Bit Manipulation (Part I)

Bit Manipulation is rarely asked during an interview. But it’s good to know all the basic concepts below in case you get asked. Personally, I haven’t run into any LeetCode questions other than the following concepts.

I. Basic concepts

a & b
a | b
~a, ~b
a ^ b (a or b, but not both)
e.g. a ^ 0 ---> a
e.g. a ^ a ---> 0
e.g. a ^ b ^ a = 0 ^ b = b
a >> num, b << num
e.g. 0000 0001 << 2 ---> 0000 0100
e.g. 1000 0000 >> 3 ---> 0001 0000
e.g. pow(2,5) is the same as (1 << 5)
a.bit_length()
e.g. a = bin(1) ---> '0b1'
b = a[2: ] ---> remove ‘ob’ prefix
e.g. a = bin(8) → ‘0b1000’
e.g. b = bin(9) → ‘0b1001’

‘b’ is in Python means binary-based

2 binary based: ‘0b’
8 octal based: ‘0.’
16 hexadecimal based: ‘0x’
a = bin(5).count('1') ---> 2

invert all the bits and add 1

E.g. -5

5 =        0000 0101
~5: 1111 1010
-5 = ~5+1: 1111 1011

E.g. -6

6 =        0000 0110
~6 = 1111 1001
-6 =~6+1 = 1111 1010

E.g. -7

7 =         0000 0111
~7 = 1111 1000
-7 = ~7+1 = 1111 1001

E.g. 5&(-5)

                   -
5 = 0000 0101
-5 = 1111 1011
5 & (-5) = 0000 0001
_

E.g. 6&(-6)

                 _
6 = 0000 0110
-6 = 1111 1010
6&(-6) = 0000 0010
_

E.g. 7&(-7)

                   -
7 = 0000 0111
-7 = 1111 1001
7 & (-7) = 0000 0001
_

E.g. 4&(4–1)

                  -
4 = 0000 0100
4-1 = 3 = 0000 0011
4 & (4-1) = 0000 0000
-

E.g. 5&(5–1)

                    -
5 = 0000 0101
5-1 = 4 = 0000 0100
5 & (5-1) = 0000 0100
_

E.g. 6&(6–1)

                 _
6 = 0000 0110
6-1 = 5 = 0000 0101
6&(6-1) = 0000 0100
_

E.g. 7&(7–1)

                  -
7 = 0000 0111
7-1 = 6 = 0000 0110
7&(7-1) = 0000 0110
_

Software Engineer