Bitwise operators and tricks!

Bit operations operate on the individual bits of the bit patterns and we perform such operations using bitwise operators. Data in memory (RAM) is organized as a sequence of bytes. Each byte is a group of eight consecutive bits. We use bitwise operators whenever we need to manipulate bits directly. Bitwise Operations are faster and closer to the system and sometimes optimize the program to a good level. Bitwise operators are language agnostic and getting hold of them can help in doing some things easily and most importantly in a shorter and sharper way.

Bitwise Operators:-

NOT (~ or !) :

• How it works

• Bitwise NOT is simply the 1s complement of a number.
• Unary operator.

AND ( & ):

• How it works

• Operates on two equal-length bit patterns, !(works on 1100 and 00)
• Binary operator.

OR ( | ):

• How it works

• Operates on two equal-length bit patterns, !(works on 1100 and 00)
• Binary operator.

XOR ( ^ ):

• How it works

• Returns 1 only if exactly one bit is set to 1 out of the two bits in comparison.
• Operates on two equal-length bit patterns, !(works on 1100 and 00)
• Binary operator.

Left Shift ( << ):

• How it works

  • Shift n number of bits to the left and append 0 at the end.

• Using this operator is equivalent to multiplying the bit pattern with 2 n ( if we are shifting n bits ) i.e.

  • 1 << 1 (shift 1 bit so 21 = 2) = 2
  • 1 << 2 (shift 2 bit so 22 = 4)= 4
  • 1 << 3 = 8

• 419 in binary 0000111110110011 << 1 = 838 (0001111101100110)

Right Shift( >> ):

• How it works

  • Shift n of bits to the right and append 1 at the end.

• Using this operator is equivalent to dividing the bit pattern by 2 n ( if we are shifting n bits ) i.e.

  • 4 >> 1(shift 1 bit so 21 = 2) = 2
  • 6 >> 1 = 3

• 220 in binary 11011100 >> 1 = 110 (1101110)

  • 221 in binary 11011101 >> 1 = same ans 110(1101110)

Observations (will help in getting hold of tricks better)

• The difference between a binary number n and n-1 is: All the bits on the right of the rightmost 1 are flipped including the rightmost 1(which will get zero). Some examples :

  • 1000 (8) -flips-> 0111 (7)
  • 0111 (7) -flips-> 0110 (rightmost 1 only got flipped, didn’t had any more towards the right)

• If 12 (1100) then -12 in binary representation will be 2’s complement of (1100) i.e 1’s complement(1100) + 1 = 0100, We traverse the one’s complement starting from rightmost bit towards left and look for 0. We flip all 1’s to 0 until we find a 0. Finally, we flip the found 0

• Two unique properties of XOR

  • n ^ n = 0
  • n ^ 0 = n

• Fenwick Tree or Binary Indexed tree

  • Helps in calculating prefix sums in an array efficiently. For example, an array is [100, -100, -1, 1, 12] the length 3 prefix [100, -100, -1] with sum 100 - 100 + -1 = -1). If you are into competitve programming or have given long contest on CodeChef then 4/5 th question generally requires you to do things like

    • Point update operation: Update the value stored at an index i.
    • Range sum query: Find the sum of a prefix of length k.

  • A Similar Data structure called Segment Trees also can be used to do things above mentioned but Fenwick tree code is much short, easier to understand and memory-efficient on the other side in a segment tree solution there exists a lot of boilerplate code. Also, both DS take O(logN) time.

• Prerequisite for Fenwick trees: How to get the last set bit? For example, For 1010, you should perform some operations to give 0010 as the output where 1 is the last set bit in 1010. For this solution is just this simple equation x ^ (x & (x - 1)) (See how sharp bitwise solutions are!)..Let's make a truth table of this to get how this equation works:

• (x & (x - 1)) this equation actually came from our observation defined in the above section. XOR(^) helps in removing 1 which exists in both results so we get the last set bit!
• We can use the above equation and Fenwick tree to maintain a partial sum tree(array to be precise). Denote BIT[] as Fenwick tree and any index we can store the sum of some numbers of any given array.

For every index i in the BIT[] array we store the cumulative sum from the index i to i - (1<<r) + 1 (both inclusive), where r represents the last set bit in the index i. So in mathematical equation this means

          {   
                a[1] + ... + a[x],     if x is power of 2
BIT[x] =                
                a[x],                  if x is odd
          }

• How (x & (x - 1)) equation played a role in above fenwick equation?

  • If we see numbers 2,4,8.. in binary form 0010,0100,1000..so on then we always get a last set bit with no other set bits(1 bit) in the representation so if r represents set bit position ex: For 4 (0100) set bit position is 3(0 for 0 ,0 for 1, 1 for 2 if read from right -> left) so
  • if i = 4 then range [i to i - (1<<r) + 1] represents 4 to 4 - (2 r = 2 2 = 4) + 1 = [4,1] i.e index 4 should contain sum of first 4 elements.
  • if i = 16 then 16(10000)-(2 r = 2 4 = 16 - 16 + 1 = 1) i.e index 16 should contain sum of first 16 elements.
  • if i = 3 then 3(0011) - (2 r = 2 0 = 1 = 3-1+1) = [3,3] i.e index 3 will contain sum of only number at index 3 or just value at index 3.

Brian Kernighan’s Algorithm

• It helps in finding no of set bits(1s) in the binary representation of a number.
• Again using our observation about x & x-1 and use it to give the rightmost set bit so if we do it again and again till we get 0 then we will get no of set bits it originally had! This is what Brian Kernighan’s algo does.

while (n) {
n = n & (n-1);
count++; 
}

Get non-repeated value from an array of duplicates

• Example array [1, 33, 54, 4, 7, 8, 8901, 33, 1, 4, 54, 8, 8901] and answer will be 7 if we use XOR operation by using its property of m ^ m = 0 && m ^ 0 = m.
• Manually lets XOR one by one and also take XOR of 7 at last so that before that we should have something like 0000 then only this property 0^7 would give us the answer.

1 ^ 33
    1   00000001
^   33  00100001
=   32  00100000

32  00100000
^   54  00110110
=   22  00010110

22 ^ 4
    22  00010110
^   4   00000100
=   18  00010010

18 ^ 8
    18  00010010
^   8   00001000
=   26  00011010

26 ^ 8901
    26      0000000000011010
^   8901    0010001011000101
=   8927    0010001011011111

8927 ^ 33
    8927    0010001011011111
^   33      0000000000100001
=   8958    0010001011111110

8958 ^ 1
    8958    0010001011111110
^   1       0000000000000001
=   8959    0010001011111111

8959 ^ 4
    8959    0010001011111111
^   4       0000000000000100
=   8955    0010001011111011

8955 ^ 54
    8955    0010001011111011
^   54      0000000000110110
=   8909    0010001011001101

8909 ^ 8
    8909    0010001011001101
^   8       0000000000001000
=   8901    0010001011000101

8901 ^ 8901
    8901    0010001011000101
^   8901    0010001011000101
=   0   0000000000000000 (Here we go!)

0 ^ 7
    0   00000000
^   7   00000111
=   7   00000111 Finally :)

Checking if the given 32-bit integer is the power of 2

• All the power of 2 have only a single bit set and using our x and x-1 observation if we perform (x & x-1) then if x is the power of 2 this will give 0 otherwise 1. So !(x & x-1) will give whether the number is the power of 2. If the case of x = 0 we don't wish to do x-1 so the final equation is

  (x && !(x & x-1))

Quick conditional assignment

• We as programmers write below code block a lot of times (literally a lot!)

if (x == a)
     x = b;
if (x == b)
     x = a;

Better way

 x = a ^ b ^ x 

If a number is even or odd

• The binary representation of an even number has no set bit at rightmost or LSB position but the odd number does so we can check like

if x & 1
      fmt.Println("ODD")
   else
      fmt.Println("EVEN")

Swap numbers without extra variables

• Using XOR we can do this for example:- Swapping i with k and vice-versa.

i = i ^ k; // i has both i and k let it be I
k = i ^ k; // remove k from I so k = i
i = i ^ k; // remove k (which is now i) from I so i = k

Thanks!