## 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 00000001printf("a = %d, b = %d\n", a, b);printf("a&b = %d\n", a & b);// The result is 00001101printf("a|b = %d\n", a | b);// The result is 00001100printf("a^b = %d\n", a ^ b);// The result is 11111010printf("~a = %d\n", a = ~a);// The result is 00010010printf("b<<1 = %d\n", b << 1);// The result is 00000100printf("b>>1 = %d\n", b >> 1);return 0;}

Output:

a = 5, b = 9a&b = 1a|b = 13a^b = 12~a = 250b<<1 = 18b>>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 -> 01100001B -> 01000010 b -> 01100010C -> 01000011 c -> 01100011As 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). Thismask 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 differencethat we have to mask here with `10111111` whichcorresponds 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