Bitwise Operations

Bitwise operators

1. The & (bitwise AND) in C or C++ takes two numbers as operands and does AND on every bit of two numbers. The result of AND is 1 only if both bits are 1.

2. The | (bitwise OR) in C or C++ takes two numbers as operands and does OR on every bit of two numbers. The result of OR is 1 if any of the two bits is 1.

3. The ^ (bitwise XOR) in C or C++ takes two numbers as operands and does XOR on every bit of two numbers. The result of XOR is 1 if the two bits are different.

4. The << (left shift) in C or C++ takes two numbers, left shifts the bits of the first operand, the second operand decides the number of places to shift.

5. The >> (right shift) in C or C++ takes two numbers, right shifts the bits of the first operand, the second operand decides the number of places to shift.

6. The ~ (bitwise NOT) in C or C++ takes one number and inverts all bits of it.

The bitwise XOR operator is the most useful operator

Tricks of Bitwise Operation:

Divide by 2

X = X>>1

Logic: When we do arithmetic right shift, every bit is shifted to right and blank position is substituted with sign bit of number, 0 in case of positive and 1 in case of negative number. Since every bit is a power of 2, with each shift we are reducing the value of each bit by factor of 2 which is equivalent to division of x by 2. Example:- x = 18(00010010) x >> 1 = 9 (00001001)

Multiplying by 2

X = X<<1

Logic: When we do arithmetic left shift, every bit is shifted to left and blank position is substituted with 0 . Since every bit is a power of 2, with each shift we are increasing the value of each bit by a factor of 2 which is equivalent to multiplication of x by 2. Example:- x = 18(00010010) x << 1 = 36 (00100100)

Bitset:

A bitset is an array of bool but each Boolean value is not stored separately instead bitset optimizes the space such that each bool takes 1 bit space only. Space taken by bitset bs is less than that of bool bs[N] and vector bs(N). Size must be known at compile time. Bitset starts its indexing backward that is for 10110, 0 are at 0th and 3rd indices whereas 1 are at 1st 2nd and 4th indices. // default constructor initializes with all bits 0 bitset<32> bset1; // bset2 is initialized with bits of 20 bitset<32> bset2(20); // bset3 is initialized with bits of specified binary string bitset<32> bset3(string("1100"));

Bit set Flip

bitset_name.flip(int pos) // Used to flip the bits

• If a parameter pos is passed, it flips the bit at the index pos only(the index pos is calculated starting from the right).

• In case no parameter is passed, it flips all the bit values converting zeros to ones and ones to zeros.

Bitset convert

bit.to_ullong() 
This function Converts the contents of the bitset to an unsigned long long int.


bit.to_ulong() 
This function Converts the contents of the bitset to an unsigned long int.

Bitset Count

 bitset<4> b1(string("1100")); 
 int result1 = b1.count(); 

The function returns the number of set bits. It returns the total number of ones or the number of set bits in the binary representation of the number.

Bitset Set

set(int index, bool val) //val = boolean 

Sets the bit to a given value at a particular index. If no parameter is passed, it sets all bits to 1.

Total number of bits in a number

log2(number)+1