## Bitwise Operations:

• 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.
• byte -- 8 bits
E.g.: from −128 to 127.
• short -- 16 bits
char -- unsigned 16 bits
• int -- 32 bits
• long -- 64 bits
• Python supports 4 primary numeric 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);
• }
• 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.
• Calculate parity. That is, return 1 (true) if the number of 1s is odd and 0 otherwise.
• Naive method:
• boolean getParity(int num) {
• boolean parity = false;
• while (num) {
• parity = !parity;
• num = num & (num - 1);
• }
• return 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).
• Get the Hamming distance.
• "The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
• Given two integers x and y, calculate the Hamming distance."
• def hammingDistance(self, x, y):
• # Result has 1 only in places where corresponding bits are different.
• z = x ^ y
• ct = 0
• # Count the number of 1s.
• while z:
• ct += 1
• # Unsets the rightmost 1.
• z &= z - 1
• return ct
darkmode