Fun with Bits

May 2, 2020

I recently stumbled across a very peculiar topic called Bit Manipulation. In most of my programming days, I haven't actually relied on the binary operation to get me the result, I know under the hood everything is converted into 0's and 1's but it was all abstraction to me.

The case was different here. While working with Bit Manipulation, I had to actually rely on arithmetic bit operations to get me to the result. So it became real interesting real soon.

Bitwise operators

Basic operation done on bits are done with bitwise operators. Since we primarily work on bits these operations are fast and are optimized to reduce time complexity.

The first three &, | and ~ are fairly straightforward. So I would briefly go over it.

&: if both bits are of equal size than & operator would compare each position and would return True/1 if input bits are True/1. Similarly for False/0.

    6       : 1 1 0
    5       : 1 0 1
            -------- &
              1 0 0

|: if both bits are of equal size than & operator would compare each position and would return True/1 if input bits differ. Similarly for False/0.

     5       : 1 0 0
     3       : 0 1 1
            --------  |
              1 1 1

~: Not operator just compliments the bit it gets. In fancy computer lingo it gives one’s complement of a number.

    5       : 1 0 1
            -------- ~
              0 1 0

Now coming to more interesting operators:

Operator	Name
`^`	XOR
`>>`	Right Shift
`<<`	Left Shift

XOR

If two bits are of two equal-size ^ of both bits in the compared position would be 1 if compared bits are of different binary and would be 0 if bot the compared bits are the same.

    6       : 1 1 0
    5       : 1 0 1
            -------- ^
              0 1 1

XOR of a number with itself is 0
```
x = "Any int number"
(x ^ x) == 0
```
XOR of a number with 0 is number itself.
```
(x ^ 0) == 0
```

Ordering in XOR does not matter, both will give the same output.

output = (7 ^ 3) ^ (5 ^ 4 ^ 5) ^ (3 ^ 4)
output = 7 ^ (3 ^ (5 ^ 4 ^ 5)) ^ (3 ^ 4)

While discussing Left Shift,<< and Right Shift, >> we will be talking about arithmetic shifts.

Left shift `<<`

Left shift shifts the binary digits by n, pads 0’s on the right.
Left shift is equivalent to multiplying the bit pattern with 2 power k( if we are shifting k bits )

1 << 1 = 2 = 1 * (2  ** 1) 
1 << 2 = 4 = 1 *(2  ** 2) 
1 << 3 = 8 = 1 * (2  ** 3)
1 << 4 = 16 = 1* (2  ** 4)
…
1 << n = 2n

Right shift `>>`

Shifts the binary digits by n, pads 0's on the left.
Right shift is equivalent to dividing the bit pattern with 2k ( if we are shifting k bits ).

4 >> 1 = 2
6 >> 1 = 3
5 >> 1 = 2
16 >> 4 = 1

Both Right shift and Left shift operators come real handy in masking.

Masking allows the user to check/change a particular bit at a particular position.

Some of the common functions associated with masking are:

Set Bit

The set bit method is generally used to SET a particular with 1.
To achieve this we would need to create a mask at the particular position where we want to SET
The mask can be created with the help of the << if the left shift operator.

def set_bit(x, position):
    mask = 1 << position
    return x | mask

set_bit(6,1)

In the above code snippet we are SETing the bit at 0th index.

    masking = 1 << 0 = 1 * (2 ** 0) 
    
    6       : 1 1 0
    1 << 0  : 0 0 1
            -------- |
              1 1 1

IS BIT SET

def is_bit_set(x, position):
    shifted = x >> position
    return shifted & 1

Clearing Bit

def clear_bit(x, position):
    mask = 1 << position
    return x & ~mask

Flip Bit

def flip_bit(x, position):
    mask = 1 << position
    return x ^ mask

Modify Bit

def modify_bit(x, position, state):
    """
    state is param that tells us to set a bit 
    or clear a bit
    """
    mask = 1 << position
    return (x & ~mask) | (-state & mask)

Observations

Bit manipulation can be used to solve problems that you are familiar with but necessarily don't know about. Here are some of my observations that I noted while using bit manipulation.

To check if the number is even

& ANDing the number with 1 gives 0 or 1 — 0 if it's even — 1 if it's odd

x = "Any int number here"
(x & 1) == 0

Practice Question

To check if the number is a power of two

If a number is x binary representation of (x-1) can be obtained by simply flipping all the bits to the right of rightmost 1 in x and also including the rightmost 1.

Let, x = 4 = (100)2
x - 1 = 3 = (011)2
Let, x = 6 = (110)2
x - 1 = 5 = (101)2

x & (x-1) will have all the bits equal to the x except for the rightmost 1 in x. In the given example below the values enclosed in || are the same for both the x and x-1 if x is not the power of 2.
If the number is neither zero nor a power of two, it will have 1 in more than one place.

Let, x = 6 = 1|1|0
(x- 1) = 5 = 1|0|1

Let,x = 16 = |1|0000
(x-1) = 15 = |0|1111

Let,x = 8 = |1|000
(x-1) = 7 = |0|111

Let,x = 23 = 1011|1|
(x-1) = 22 = 1011|0|

x = "Any int number here"
(x & x-1) == 0

There are a lot more things that can be done with just bits and are definitely not limited to the above observations. Try to find your own observations. Happy coding!