Basics

  • C++ type int is a 32-bit type, which means that every int number consists of 32 bits

  • Below is a reminder of basic use of all bit wise operators.

// C Program to demonstrate use of bitwise operators
#include <stdio.h>
int main()
{
// a = 5(00000101), b = 9(00001001)
unsigned char a = 5, b = 9;
// The result is 00000001
printf("a = %d, b = %d\n", a, b);
printf("a&b = %d\n", a & b);
// The result is 00001101
printf("a|b = %d\n", a | b);
// The result is 00001100
printf("a^b = %d\n", a ^ b);
// The result is 11111010
printf("~a = %d\n", a = ~a);
// The result is 00010010
printf("b<<1 = %d\n", b << 1);
// The result is 00000100
printf("b>>1 = %d\n", b >> 1);
return 0;
}

Output:

a = 5, b = 9
a&b = 1
a|b = 13
a^b = 12
~a = 250
b<<1 = 18
b>>1 = 4
  • The left shift and right shift operators should not be used for negative numbers. also, 1<<33 is undefined if integers are stored using 32 bits.

  • The bitwise XOR is the most important for technical interviews. E.g. Find the only number that is occuring odd mumber of times problem.

  • The & operator can be used to quickly check if a number is odd or even. How? See this case, an odd number in its binary form will also have 1 in its LSB (Least Signifcant Bit). This means if x if odd then x&1 will always return non-zero number. Like 101 & 001 = 001, while 100 & 001 = 0 and so on.

  • Setting a bit means that if K-th bit is 0, then set it to 1 and if it is 1 then leave it unchanged.

  • Clearing a bit means that if K-th bit is 1, then clear it to 0 and if it is 0 then leave it unchanged.

  • Toggling a bit means that if K-th bit is 1, then change it to 0 and if it is 0 then change it to 1.

For more reference on the above three, check here.

Bit Tricks that I didn't know till yet

  • Upper Case English aplhabets to lower case:
ch |= ' ';
//Output a
/*
Logic:
A -> 01000001 a -> 01100001
B -> 01000010 b -> 01100010
C -> 01000011 c -> 01100011
As we can see if we set 5th bit of upper case characters,
it will be converted into lower case character.
We have to prepare a mask having 5th bit 1 and other 0 (00100000). This
mask is bit representation of space character (‘ ‘).
The character ‘ch’ then ORed with mask.
Example-
ch = ‘A’ (01000001)
mask = ‘ ‘ (00100000)
ch | mask = ‘a’ (01100001)
*/
  • Lower to Upper Case:
ch |= '_';
/* Same logic as in the previous, just the difference
that we have to mask here with `10111111` which
corresponds to underscore.
*/
  • Count set bits in an integer (i.e number of 1s in binary):

    • Brian Kernighan's Algorithm:

      #include <iostream>
      using namespace std;
      class csb {
      public:
      unsigned int countSetBits(int n)
      {
      unsigned int count = 0;
      while(n) {
      n &= (n-1);
      count++
      }
      return count;
      }
      };
      int main();
      {
      csb g;
      int i = 9;
      cout << g.countSetBits(i);
      return 0;
      }

      Explaination: n = 9 (1001) count = 0

      Since 9 > 0, subtract by 1 and do bitwise & with (9-1) n = 9&8 (1001 & 1000) n = 8 count = 1

      Since 8 > 0, subtract by 1 and do bitwise & with (8-1) n = 8&7 (1000 & 0111) n = 0 count = 2

      Since n = 0, return count which is 2 now.

      Complexity: O(logn)

    • Lookup Table Approach: Still have to understand but has O(1) Complexity. Reference can be found here

Rest of the things I learned from here

© 2021 Mritunjay Sharma