play with bitwise operations

1. num OR with 1 –> num will always be 1

2. num AND with 0 –> num will always be 0

Some useful bitwise operations with examples:

1. Multiply a number by 2 –> Left shift the number by 1:

   $$
   exp: 5 (00000101) –> 10 (00001010)
   $$

2. Divide a number by 2 –> Right shift the number by 1:
   $$ $$

3. Powers of 2 –> Right shift 1 by (exponent):

   $$
   exp: 4 = 1 times 2 times 2 = 2^2, 8 = 1 times 2 times 2 times 2 = 2^3
   $$

4. Check if number is power of 2 –> $textbf{(n&(n-1) == 0)}$:

   $$16 (00010000) \ 15 (00001111)$$

5. Decimal to binary –> Loop and number&1:

   Right shift the decimal number by 1 each time (first time do AND first) and AND that with 1, record it down. Print all the recorded digits in reversed order to get the binary representation of the decimal number.

6. Check even/odd numbers –> number AND with 1:

   1 2 3 4

   if n&1 == 0: n is EVEN else: n is ODD

7. Check $x_{th}$ bit from right in number n –> AND with 1 shifted to the left by $x$ bits

   1 2 3 4

   if n&(1<<x-1) == 0: RESET else: SET

   Arithmetic operators have higher priority than bitwise operator. $x-1$ will be evaluated before $>>$.

8. Set the $x_th$ bit in the number –> OR with 1 shifted to $x_th$ bit:

   1	n = n | (1<<x-1)

9. Toggle the $x_th$ bit in the number –> XOR with 1 shifted to $x_th$ bit

   1	n = n ^ (1<<x-1)

10. Reset the rightmost bit in a number n:

    1	n = n & (n-1)

11. Check the bit-length:

    1 2 3 4

    l = 0 while n: l += 1 n >>= 1

12. Count the number of set bits:

    1 2 3 4

    cnt = 0 while n: cnt += 1 n &= (n-1)

Finally, an example of getting all the subsets/sublists of a set/list using bitwise operation. Here is a simple example:

In this example, we are trying to get all the sublists of a list [0, 1, 2], implemeting this in Python:

1
2

n = 3
[[j for j in range(n) if (i>>j)&1] for i in range(2**n)]

There are three numbers in the original list and each number can only have two states: in or not in the list. Therefore, there should be $2^3 = 8$ sublists of the original list. Let me further illustrate this idea with a table, each table cell value is the result of (row>>col)&1: