Basics
 Computers take instructions in binary, i.e. no or yes, or 0 or 1.
Bit
 BIT is a short form for Binary digIT
 A bit is a numeric value representing one of the two states, 0 or 1, no or yes, etc.
 A bit's states are normally represented as 0 and 1.
 A 'Set' bit is a bit with value of 1.
 'Clearing' a bit means setting its value to 0.
Byte
1 byte = 8 bits
 A byte is a sequence of 8 bits.
 Hard Disk and RAM capacities are measured in bytes.
 A byte can have 2^8 values, ie 256 values, or values from 0 to 2^81, or 0 to 255.
 for an unsigned int, a byte can represent values from 0 to 255.
 for a signed int, a byte can represent values from 128 to 127.
Basics of Boolean Algebra
 OR (this or that)
 symbol is ''
 0  0 = 0
 0  1 = 1
 1  0 = 1
 1  1 = 1
 AND (this and that)
 symbol is '&'
 0 & 0 = 0
 0 & 1 = 0
 1 & 0 = 0
 1 & 1 = 1
 XOR (ExclusiveOR) (this or that, but not both)
 symbol is '^'
 A ^ B will set the bits to 0 where A and B have same bits, and to 1 where the bits are different.
 0 ^ 0 = 0
 1 ^ 0 = 1
 0 ^ 1 = 1
 1 ^ 1 = 0
 Complement (not this)
 symbol is '~'
 flips the bits, 0 to 1, and vice versa.
 ~0 = 1
 ~1 = 0
 Left Shift
 symbol is '<<'
 x << y means x shifted y bits to the left.
 If you run out of space, bits drop off from the left.
 Right Shift
 symbol is '>>'
 x >> y means x shifted y bits to the right.
 If you run out of space, bits drop off from the right.
Additional
 OR
 OR is used for setting a bit regardless of the other bit.
 When you want to set a bit to 1, just 'OR' the bit with 1
 If x denotes a bit(0 or 1), then the following hold true.
 x  0 = x (i.e. OR ing with 0 retains the original bit.)
 x  1 = 1 (i.e. OR ing with 1 sets the bit to 1.)
 123456
// prints 1
System.out.println(
0

1
);
// prints 1
System.out.println(
1

1
);
 AND
 AND can be used for clearing a bit.
 When you want to 'clear' a bit, just 'AND' it with 0.
 AND can be used for checking whether a bit is set.
 To check whether a bit is set, just 'AND' it with 1, it will return whether that bit was set.
 If x denotes a bit(0 or 1), then the following hold true.
 x & 0 = 0 (i.e. AND ing with 0 clears the bit to 0)
 x & 1 = x (i.e. AND ing with 1 retains the original bit)
 123456
// prints 0
System.out.println(
0
&
1
);
// prints 1
System.out.println(
1
&
1
);
 XOR
 for flipping selective bits, XOR is chosen.
 for flipping a bit, XOR it with 1, it will get reversed.
 If x denotes a bit(0 or 1), then the following hold true.
 x ^ 1 = ~x (XOR ing with 1 flips the bits)
 123456
// prints 1, because XOR flips the bit.
System.out.println(
0
^
1
);
// prints 0, because XOR flips the bit.
System.out.println(
1
^
1
);
 NOT
 The bitwise complement operator, ~, flips every bit in a number.
Usages
 N << 1 = N*2
 N << 2 = N*pow(2,2)
 N << k = N*(pow(2,k))
 N >> 1 = floor(N/2)
 N >> 2 = floor(N/pow(2,2))
 N >> k = floor(N/pow(2,k))
 N & 1 = last bit in N
 N & 3 = last 2 bits in N
 N & 7 = last 3 bits in N
 N & (pow(2, k)1) = last k bits in N
 ~N + 1 = N
 N & 0xFF = least significant byte of integer or the last 8 bits of integer.
 An Integer normally has 4 bytes(32 bits)
 F in hex is 1111 in binary, so FF(or 0xFF) is 11111111 in binary
 Doing N & 0xFF removes the first 3 bytes and only keeps the last byte(8 bits) of integer
 Eg 1783 in binary is 11011110111
 1783 & 0xFF only keeps the last 8 bits of 11011110111, and is, 11110111, which is 247
Example Interview Questions
Multiply a no by 2
 left shift N by 1
 N << 1
 12345
int
n =
17
;
// prints 34
System.out.println(n <<
1
);
Divide a no by 2
 right shift N by 1
 N >> 1
 12345
int
n =
17
;
// prints 8
System.out.println(n >>
1
);
set the kth bit of N(counting from right) to 1.
 take 1, shift it k1 places left, so its at kth place.
 do 'OR' with N.
 N = N  (1 << (k1))
 12345678910111213
int
n =
17
;
// prints "10001"
System.out.println(Integer.toBinaryString(n));
int
k =
3
;
// sets the 3rd bit from right to 1;
n = n  (
1
<< (k
1
));
// prints "10101";
System.out.println(Integer.toBinaryString(n));
clear the kth bit of N(counting from right).
 take 1, shift it k1 places left, so its at kth place.
 inverse it, so it becomes 0 and everything else is 1
 do 'AND' with N.
 N = N & ~(1 << (k1))
 123456789101112
int
n =
20
;
// prints "10100"
System.out.println(Integer.toBinaryString(n));
int
k =
3
;
// clears the 3rd bit from right to 0;
n = n & ~(
1
<< (k
1
));
// prints "10000";
System.out.println(Integer.toBinaryString(n));
toggle/flip the kth bit of N(counting from right).
 Remember the XOR is used for flipping(changing/reversing) the bit
 take 1, shift it k1 places left, so it is at kth place.
 do 'XOR' with N.
 N = N ^ (1 << (k1))
 123456789101112
int
n =
20
;
// prints "10100"
System.out.println(Integer.toBinaryString(n));
int
k =
3
;
// toggle the 3rd bit from right;
n = n ^ (
1
<< (k
1
));
// prints "10000";
System.out.println(Integer.toBinaryString(n));
turn off the first set bit(1 bit) of a number N.
 N1 will have all bits reversed before and including the first bit set.
 N & (N1) will turn off the first set bit.
 N & (N1)
 1234567891011
int
n =
20
;
// prints "10100"
System.out.println(Integer.toBinaryString(n));
// n1 will have all bits reversed before and including the first bit set
// n & (n1) will turn off the first set bit
n = n & (n
1
);
// prints "10000";
System.out.println(Integer.toBinaryString(n));
get the count of 1s in a no.
1
2
3
4
5
6
7
8
9
10
 // Idea: N & 1 gives the first bit. int count = 0 ; while (n > 0 ) { count = count + (N & 1 ); N = N >> 1 ; } return count; 
Alternate method: suggested by thevagabond85 in comments.
1
2
3
4
5
6
7
8
9
 int count = 0 ; while (n) { n = n & (n 1 ); // turn off the first set bit(1 bit) of a number N. count++; } return count; 
How to calculate the no of bits to convert from no A to no B.
 Remember that for flipping a bit, XOR is chosen.
 A XOR B will give you 1 wherever the bits are different and you need to change bits.
 now we need to count the no of 1s in C, which is done by above method
 the result is no of set bits(1 bits) in A ^ B
 12345678910111213141516171819202122232425
int
n1 =
20
;
int
n2 =
30
;
// prints "10100"
System.out.println(Integer.toBinaryString(n1));
// prints "11110"
System.out.println(Integer.toBinaryString(n2));
// n1 ^ n2 will give you 1, wherever the bits are different(you need to change)
int
n = n1 ^ n2 ;
// count the no of 1s in n, by above method;
int
count =
0
;
while
(n >
0
) {
count = count + (n &
1
);
n = n >>
1
;
}
// prints 2,
// two bits required to change from 10100 to 11110
System.out.println(count);
Check if N is a power of 2 or not.
 if N is a power of 2, it will have only one 1, and rest all 0s.
 if N is a power of 2, N1 will have all 1s, except that the 1 bit of N will be converted to 0.
 so, if N is a power of 2, then (N & (N1) == 0)
 1234567891011121314
int
n1 =
20
;
int
n2 =
32
;
// n = power of 2 will have one 1 followed by all 0s.
// n1 will have one 0 followed by all 1s.
// n & (n1) is 0 for power of 2, and 1 otherwise.
// prints false, becase 20 is not a power of 2.
System.out.println((n1 & (n1
1
)) ==
0
);
// prints true, because 32 is a power of 2.
System.out.println((n2 & (n2
1
)) ==
0
);
Check if N is a power of 4 or not.
 check that N is a power of 2(from above)
 check that there are a total of even 0s in the binary representation of N.
How to get the last 3 bits of an integer.
 we just do AND with 111.
 N & ((1 << 3)1)
 123456789101112131415
int
n =
22
;
int
k =
3
;
// prints "10110"
System.out.println(Integer.toBinaryString(n));
// take 1, shift it k digits left, and subtract 1,
// so that k 1s are left, 1111...k times.
// now do, AND with n, it will give last k digits of n
n = n & ((
1
<< k) 
1
);
// prints "110", last 3 digits of "10110"
System.out.println(Integer.toBinaryString(n));
Get the 5 highest bits of an integer(8 bit integer).
 for getting the 5 highest bits, we will remove the lower 3 bits and do 'AND' with 11111.
 we create 11111 by left shifting 1 by 5, 1 << 5, which gives 100000, and subtracting 1, which gives 11111.
 so we create 11111 by (1 << 5)1
 we remove the lower 3 bits of x by (x >> 3)
 Doing 'AND' gives us the final answer.
 (x >> 3) & ((1 << 5)1)
check whether the kth bit in N is 1.
 take 1, shift 1 by k1 to the left, (1 << (k1))
 Do N AND above, ie N & (1 << (k1))
 The above result will have all digits 0, except the most significanr digit, which will be 0 if the nth bit in x is 0.
 So, if the nth significant bit in x is 0, then expression x & (1 << (n1)) will be 0.
 So, if the nth significant bit in x is 1, then expression x & (1 << (n1)) will not be 0.
 N & (1 << (k1)) != 0
swap two nos using bitwise operations.
 A = A ^ B
 B = A ^ B
 A = A ^ B
 Note that (A ^ B) ^ B => (flips every bit of 'A' twice or zero times, essentially which means gives back 'B').
 Note that (A ^ B) ^ ((A ^ B) ^ B) => (A ^ B) ^ A => B => (flips every bit of 'B' twice, essentially giving back 'B')
swap even and odd bits in a no(4 byte integer)
 (N & 0xaaaaaaaa) gives the even bits(because a is 1010, so aa is 10101010, doing & with N, gives the even bits)
 (N & 0x55555555) gives the odd bits(because 5 is 0101, so 55 is 01010101, doing & with N, gives the odd bits)
 (N & 0xaaaaaaaa) >> 1 shifts even to odd bits
 (N & 0x55555555) << 1 shifts odd bits to even bits.
 ((N & 0xaaaaaaaa) >> 1)  ((N & 0x5555555555) << 1) gives us the required no where even and odd bits are swapped.
Misc
 IP address
 normally represented as A:B:C:D
 has 4 bytes, each of A, B, C, D representing a byte(8 bits).
 each of A, B, C, D is 1 byte or 8 bits, and can have values from 0 to 255
 Right most bit(assuming 16 bit integer)???
 N & 0xff;
 Left most bit(assuming 16 bit integer)???
 (N>>8) & 0xff;
 Sign bit(assuming 16 bit integer)???
 N & 0x8000;
Binary representation of a given number
void bin(unsigned n)
{
unsigned i;
for (i = 1 << 31; i > 0; i = i / 2)
(n & i)? printf("1"): printf("0");
}
void bin(unsigned n)
{
if (n > 1)
bin(n/2);
printf("%d", n % 2);
}
Check if binary representation of a number is palindrome
int x = 1<<31 + 1; // Let us take x be 1000000000001
int h_byte = (x & 0xffff0000) >> 16 ;
int l_byte = (x & 0x0000ffff) << 16;
int y;
y = l_byte  h_byte;
if(x == y) {
cout<<"palindrome!!";
}
XOR Approach:
(Assuming 32 bit int as an input)
int a = num & 0xFFFF0000;
int b = num & 0x0000FFFF;
if (a ^ b == 0) then palindrome, otherwise not.
Detect if two integers have opposite signs
bool oppositeSigns(int x, int y)
{
return ((x ^ y) < 0);
}
bool oppositeSigns(int x, int y)
{
return ((x ^ y) >> 31);
}
Function to find minimum of x and y
int min(int x, int y)
{
return y + ((x  y) & ((x  y) >>
(sizeof(int) * CHAR_BIT  1)));
}
Rotate bits of a number
n > number , d>digits
left rotate :: (n << d)(n >> (INT_BITS  d)
right rotate :: (n >> d)(n << (INT_BITS  d))
Round up to the next highest power of 2
unsigned int v; // compute the next highest power of 2 of 32bit v v; v = v >> 1; v = v >> 2; v = v >> 4; v = v >> 8; v = v >> 16; v++;
Let us try for 17(10001) step 1 n = n  1 = 16 (10000) step 2 n = n  n >> 1 n = 10000  01000 n = 11000 n = n  n >> 2 n = 11000  00110 n = 11110 n = n  n >> 4 n = 11110  00001 n = 11111 n = n  n >> 8 n = 11111  00000 n = 11111 n = n  n >> 16 n = 11110  00000 n = 11111 step 3: Return n+1 We get n + 1 as 100000 (32)
Function __builtin_clz
This builtin method is provided by GCC to count the number of leading zero’s in variable. The Syntax:It takes the input parameter as a number for which the the count of leading zero’s is to be determined. It returns the count of leading zero’s as expected. Taking for example, lets take a number 16. An int takes 4 bytes in gcc. Its binary representation isCode:int __builtin_clz (unsigned int x)Counting the number of leading zero’s is 27 which should be our result for this case..Code:00000000 00000000 00000000 00010000Function __builtin_ctz
This builtin method by GCC determines the count of trailing zero in the binary representation of a number. The Syntax:The input parameter is the number for which the the count of trailing zero’s is to be determined. It returns the count of trailing zero’s as expected. Taking for example, lets take the same number 16. Again, an int takes 4 bytes in gcc. Its binary representation isCode:int __builtin_ctz (unsigned int x)Counting the number of trailing zero’s is 4 which should be our result for this case..Code:00000000 00000000 00000000 00010000Function __builtin_popcount
This builtin method by GCC determines the number of one’s in the binary representation of a number. The Syntax:The input parameter is the number for which the the number of 1’s is to be determined. It returns the count of set bits as expected.. Taking for example, lets take the same number 16. Again, an int takes 4 bytes in gcc. Its binary representation isCode:int __builtin_popcount (unsigned int x)Counting the number of one’s is just 1, which should be our result for this case..Code:00000000 00000000 00000000 00010000Complete Example
Here is a complete example program which demonstrates the use of these builtin methods.On running the above example program, here is our output:Code:#include <stdio.h> #include <stdlib.h> int main() { int num = 16; int clz = 0; int ctz = 0; int ones = 0; clz = __builtin_clz(num); printf("Number of leading zero's in %d is %d\n", num, clz); clz = __builtin_clz(num); printf("Number of leading zero's in %d is %d\n", num, clz); ctz = __builtin_ctz(num); printf("Number of trailing zero's in %d is %d\n", num, ctz); ones = __builtin_popcount(num); printf("Number of one's in %d is %d\n", num, ones); return 0; }Great! it works fine as per our understanding. Note, it even worked fine for negative numbers which are stored as two’s complement.Code:Number of leading zero's in 16 is 27 Number of leading zero's in 16 is 0 Number of trailing zero's in 16 is 4 Number of one's in 16 is 1
Code to find the Greatest Common Divisor of two numbers.
Compute the integer absolute value (abs) without branching.

int r; // the result goes here
int const mask = v >> sizeof(int) * CHAR_BIT  1;
r = (v + mask) ^ mask;
Compute the minimum (min) or maximum (max) of two integers without branching.
int y;
int r; // the result goes here
r = y ^ ((x ^ y) & (x < y)); // min(x, y)
r = x ^ ((x ^ y) & (x < y)); // max(x, y)
Reversing a bits in an integer:
x = ((x & 0xaaaaaaaa) >> 1)  ((x & 0x55555555) << 1);
x = ((x & 0xcccccccc) >> 2)  ((x & 0x33333333) << 2);
x = ((x & 0xf0f0f0f0) >> 4)  ((x & 0x0f0f0f0f) << 4);
x = ((x & 0xff00ff00) >> 8)  ((x & 0x00ff00ff) << 8);
x = ((x & 0xffff0000) >> 16)  ((x & 0x0000ffff) << 16);
Counting number of bits:
while(n) { n = n & (n1); count++; } return count;
Upper Case into Lower Case
"CAPITAL LETTER" XOR " " = "small letter" "W" XOR " " = "w" "g" XOR " " = "G"
Comments
Post a Comment