If you have any doubts in the below, contact us by dropping a mail to the Kung Fu Panda.
We will get back to you very soon.
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^8-1, 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 (Exclusive-OR) (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.)
// 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)
// 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)
// 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
int n = 17;
// prints 34
System.out.println(n << 1);
Divide a no by 2
right shift N by 1
N >> 1
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 k-1 places left, so its at kth place.
do 'OR' with N.
N = N | (1 << (k-1))
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 k-1 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 << (k-1))
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 k-1 places left, so it is at kth place.
do 'XOR' with N.
N = N ^ (1 << (k-1))
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.
N-1 will have all bits reversed before and including the first bit set.
N & (N-1) will turn off the first set bit.
N & (N-1)
int n = 20;
// prints "10100"
System.out.println(Integer.toBinaryString(n));
// n-1 will have all bits reversed before and including the first bit set
// n & (n-1) 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.
// 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.
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
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, N-1 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 & (N-1) == 0)
int n1 = 20;
int n2 = 32;
// n = power of 2 will have one 1 followed by all 0s.
// n-1 will have one 0 followed by all 1s.
// n & (n-1) 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)
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 k-1 to the left, (1 << (k-1))
Do N AND above, ie N & (1 << (k-1))
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 << (n-1)) will be 0.
So, if the nth significant bit in x is 1, then expression x & (1 << (n-1)) will not be 0.
N & (1 << (k-1)) != 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 'A').
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