# 2)Bitwise Operations:

## 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

- byte -- 8 bits
- Python supports 4 primary numeric types:

https://docs.python.org/2/library/stdtypes.html- 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.

- ^ (XOR)
- Common (and not-so-common) bit tasks:
- Get the value of the bit at i in num. Specifically, return whether the
*i*th 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
*i*th 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*i*th bit is 0. In the first case, the*i*th bit must be 0; in the second, it must be 1.

- boolean getBit(int num, int i) {
- Set num's
*i*th 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
*i*th 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.

- int setBit(int num, int i) {
- Clear num's
*i*th bit. Specifically, set the*i*th 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
*i*th one, which will become a 0 if it isn't already.

- int clearBit(int num, int i) {
- Update num's
*i*th bit with*v*. Specifically, set the*i*th 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
*i*th bit. Next, left-shift v by i bits so that v becomes a number where the*i*th bit is equal to what v was and all the other bits are 0. Finally, OR with the modified num (*i*th bit cleared) so that num's*i*th 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.

- int updateBit(int num, int i, int v) {
- 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.

- int clearRightmost(int num) {
- Calculate parity. That is, return 1 (true) if the number of 1s is odd and 0 otherwise.

EPI 5.1. #link http://www.geeksforgeeks.org/write-a-c-program-to-find-the-parity-of-an-unsigned-integer/ and https://graphics.stanford.edu/~seander/bithacks.html#OperationCounting- 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.

- boolean getParity(int num) {
- 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).

- Naive method:
- Get the Hamming distance.

https://leetcode.com/problems/hamming-distance/#/description- "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

- Get the value of the bit at i in num. Specifically, return whether the