Bit Manipulation
We have binary computers, that is they operate on bits. So if we can utilize this property clearly we can greatly improve the efficiency of our algorithm.
how to get the total no of bits for a data type
// to get the no of bits for a data type
int noBits = sizeof int * 8;
list of bitwise operators
&
and - this operators do and of two numbers|
or - this does the or of bits of two numbers~
not - this inverts all the bits in the number^
xor - this does the xor, xor of two bits is true if both bits are different<<n
left shift - this shift the bits to leftn
no of times, the bits are filled with 0.>>n
right shift - this shift the bits to rightn
no of times, the new bits are filled with 0.
notes
- The result of a right-shift of a signed negative number is implementation-dependent.
So better not use
-2 >> 3
. - If the
n
is negative the it is undefined behavior.
how to check if i'th bit is set or not - use and
int i=3; // bit to get
int n = 132;
int t = n & (1 << i); // check bit set
flip the i'th bit - use xor
int i = 5; // bit to filp
int n = 32432;
int t = n ^ (1 << i); // new no with bit flipped
Compute xor from 1 to n
int n = 100;
case(n%4){
0: return n;
1: return 1;
2: return n+1;
3: return 0;
}
// how this works? - because at intervals of 4 each bit have repeated twice
// this is clearly visible for 2^n - 1
// but even for cases where n % 4 == 0, the bits have repeated twice
// after which the n comes because, 0 ^ n = n
// after this we get 1, and then n + 1, then 0
set bit at position p
int n = 123;
int p = 10;
n = n & (~(1 << p));
powers of 2
check if no is power of two
int x = 21312;
if(x==0) return true;
if(!(x & (x-1))) return true;
// ans of x ans x - 1 is 0 if it is power of 2
multiply divide by 2
int x = 213;
int y = x >> 1; // divide by 2
int z = x << 1; // multiply by 2
MSB - LSB
- MSB - most significant bit - the leftmost set bit
- LSB - least significant bit - first bit to right
get the rightmost set bit
int x = 1021;
// get a new no with only its right most bit set
// to that of the no
// 10100 -> 00100
int y = x ^ (~x + 1);
// or
int y = x ^ -x; // because -x = ~x + 1 two's complement
unset the rightmost set bit
int x = 21312;
int y = x & (x-1);
clear all bit from lsb to ith bit
// [xxxxxi....0]
int x = 1312;
int i = 4;
int mask = ~((1 << i+1 ) - 1);
x &= mask;
clear all bit from msb to ith bit
// [xx1...ixxxx] [1...i] this will be 0
mask = (1 << i) - 1;
x &= mask;
get the msb
int n = 123;
// the msb will make it's right adjacent element 1 so now 2 elements are 1
n = n | (n & n >> 1);
// now make 4 1's with 2 1's
n = n | (n & n >> 2);
// now make 8 1's with 4 1's
n = n | (n & n >> 4);
// now make 16 1's with 8 1's
n = n | (n & n >> 8);
// now make 32 1's with 16 1's
n = n | (n & n >> 16);
// now the number will be all 1's to its msb
// so we now add 1 and right shift 1 to get it
// this would overflow on last bit so check if it is last bit too
return ((n+1) >> 1) | (n & (1<<31));
upper case to lower case
char c= 'd';
c ^= 32; // for ascii value character only
Problems solved using bitwise
- all no are repeated even no of time expect one find it
- do xor of all elements
- swap two numbers without additional variable and arithmetic operators
x = x ^ y;
y = x ^ y;
-x ^y ^ y
which isx
so nowy
havex
valuex = x ^ y;
-x ^y ^ x
which isy
q
- find to non-repeating elements
x
andy
, all other elements repeat twice- do xor of all elements you wil get
x ^ y
as other will cancel out. - now if two no are different, which is the first bit they differ on, it would be the rightmost set bit of their xor( xor is true only if things differ)
- so you divide no into group according to the right most bit of xor, and then do xor of the two groups separately. and you will get both no.
- do xor of all elements you wil get