Integers are represented as a string of bits (binary digits). Either big endian (akin to most significant place value at left) or little endian (akin to most significant place value at right). So three-hundred twenty-one as 321 or 123.
If unsigned integer, the number of bits used (the width) determines the numbers that can be encoded: 2^n. Unsigned means that the number is always positive; negatives aren't supported.
If signed integer, 4 methods; most common is 2's complement where negating a number (whether positive or negative) is done by inverting all the bits and then adding 1.
This has the advantage of having only one representation of 0 (instead of negative 0 and positive 0).
With 2's complement: "a signed integral type with n bits [...] represent[s] numbers from −2^(n−1) through 2^(n−1) − 1." So with 8 bits, the numbers from -128 to 127 can be encoded.
Java supports the following 2's complement signed numerical primitives (does not support unsigned numbers really): Also called integral data types.
int -- Implemented using C's long, giving at least 32 bits of precision.
float -- Implemented using C's double, number of bits of precision depends on machine.
long -- Unlimited precision; expands to the limit of the available memory (not limited by number of bits).
complex -- Have a real and imaginary part, each of which is a float.
There are also fractions -- that hold rationals -- and decimal -- that hold floating-point numbers with user-definable precision.
Arithmetic:
Adding works as normal. Just remember that 1 + 1 = 10, so gotta carry the 1.
With subtraction, as normal but just be careful with borrowing from the left. If substracting 1 from 0 (0 - 1), borrow from the first place to the left where it's 1 - 0. If have to borrow multiple times, the leftmost digit (the one I'm really borrowing from) becomes a 0, the intervening digits get a decimal place added to them and then since they get borrowed from too a 1 is subtracted (so a 0 becomes 10 then 1 and a 1 becomes 11 then 10), and the original digit that needed to be increased becomes a 10. http://sandbox.mc.edu/~bennet/cs110/pm/sub.html
Multiplication can be done with left bitshifts. So because 3 * 5 is equivalent to 3 * (4 + 1), you can bitshift 3 to the left 2 places (which is 3 * 2^2 = 3 * 4) and then add 3 (3 * 1) back in.
Division can be done with right bitshifts, but just remember that it's integer division--rounded down basically.
Bitwise operations:
& = AND
^ = XOR
| = (inclusive) OR
x << n = left-shifts x by n places (0s appended at the end). Equivalent to x * 2^n
x >> n = right-shifts x by n places using sign extension. Equivalent to x / 2^n (integer division). In Python, right-shift 0-fills.
x >>> n = right-shifts x by n places where 0s are shifted into the leftmost spots. Only in Java.
~ = flips bits (unary operator)
Bit facts & tricks: Since operations are bitwise (occur bit by bit), these are all equivalent to their series-equivalents. E.g.: x ^ 0 is the same as x ^ 0s. If a statement is true for a single bit, it's true for a sequence of bits.
^ (XOR)
x ^ 0 = x
x ^ 1 = ~x ~ = negation
x ^ x = 0
& (AND)
x & 0 = 0
x & 1 = x
x & x = x
| (inclusive OR)
x | 0 = x
x | 1 = 1
x | x = x
Swapping two values without a temporary variable:
a = a ^ b
b = a ^ b
a = a ^ b
E.g.: a = 2, b = 3; a = 0010, b = 0011.
a = a ^ b = 0010 ^ 0011 = 0001
b = a ^ b = 0001 ^ 0011 = 0010
a = a ^ b = 0001 ^ 0010 = 0011
a = 3, b = 2.
Common (and not-so-common) bit tasks:
Get the value of the bit at i in num. Specifically, return whether the ith bit is 1.
boolean getBit(int num, int i) {
return ((num & (1 << i)) != 0);
}
First left-shift 1 by i to get something like 00100000. Then AND with num to clear (set to 0) all the bits except the ith bit. If that value is not 0, then it's 1 and return true. Else it's 0 so return false.
To be more precise, the ANDing doesn't quite clear. It just makes it so that there are only two cases: all the bits are 0 or all the bits except the ith bit is 0. In the first case, the ith bit must be 0; in the second, it must be 1.
Set num's ith bit to 1.
int setBit(int num, int i) {
return num | (1 << i);
}
First left-shift 1 by i to again get something like 00100000. Then OR with num so that the ith bit will become 1 and the other values will not change. Recall that x OR-ing with 1 will always result in 1 and that x OR-ing with 0 will not change x.
Clear num's ith bit. Specifically, set the ith bit to 0.
int clearBit(int num, int i) {
int mask = ~(1 << i);
return num & mask;
}
Do something like the inverse of set (naturally). Left-shift 1 by i to again get something like 00100000. Then invert it so it looks like 11011111. AND with num: ANDing with 1 doesn't change anything, so the only bit that will change is the ith one, which will become a 0 if it isn't already.
Update num's ith bit with v. Specifically, set the ith bit to v.
int updateBit(int num, int i, int v) {
int mask = ~(1 << i);
return (num & mask) | (v << i);
}
The first part is equivalent to the clear bit method. Create a mask that looks like 11011111 then AND with num to clear the ith bit. Next, left-shift v by i bits so that v becomes a number where the ith bit is equal to what v was and all the other bits are 0. Finally, OR with the modified num (ith bit cleared) so that num's ith bit becomes 1 if v is 1 or is otherwise left as 0--recall that no other bits in num are modified since ORing with a 0 does not change the original.
Clear (unset) rightmost set bit. That is, change rightmost 1 to 0.
int clearRightmost(int num) {
return num & (num-1);
}
So, e.g., a 12 (1100) becomes a 1000 since ANDing 1100 and 1011 is 1000.
This forms the basis of the operation to determine parity.
Each time through the loop (until num is 0), clear the rightmost set bit and invert parity. Every odd number of clears, parity will be true / 1, so in the end, parity will be 1 if the number of 1s is odd and 0 otherwise.
Time complexity is the number of set bits.
We can also get the rightmost bit and xor with a 0/1 result. If 0, result doesn't change. Otherwise, result flips.
Not-so-naive method uses a precomputed lookup table. So for example the table could have the parities of the values from 0 through 15 inclusive. And then to find the parity of a 64 bit number, you would go 16 bits at a time by right shifting and XORing the 16 bit parities together.
This works because bitwise operations are associative (i.e., the grouping doesn't matter).
No comments