1203. Algorithm - Bit ManipulationXor and Shifting
Bit Manipulation.
1. Operations for Bit
- & (And)
- | (OR)
- ^ (XOR)
- ~ (Negative)
2. Common Facts
XOR | AND | OR |
---|---|---|
x ^ 0s = x | x & 0s = 0 | x | 0s = x |
x ^ 1s = ~x | x & 1s = x | x | 1s = 1 |
x ^ x = 0 | x & x = x | x | x = x |
3. Shifting
- Arithmetic Right Shift (take the sign bit to most significant bit)
- Logical Right Shift (alway shift zero to most significant bit)
See the difference through the below sample.
public static void main(String[] args) {
// output 0, shift 0, since it is positive, finally becomes to 00000000 00000000 00000000 00000000
System.out.println(repeatArithmeticShift(34543,40));
// output 0, logical shift always append a zero into the most significant bit repeatedly.
System.out.println(repeatLogicShift(34543,40));
// output -1, shift 1, since it is negative, finally becomes to 11111111 11111111 11111111 11111111
System.out.println(repeatArithmeticShift(-34543,40));
// output 0, logical shift always append a zero into the most significant bit repeatedly.
System.out.println(repeatLogicShift(-34543,40));
}
public static int repeatArithmeticShift(int x, int count) {
for (int i = 0; i < count; i++) {
x >>= 1; //Arithmetic shift by 1
}
return x;
}
public static int repeatLogicShift(int x, int count) {
for (int i = 0; i < count; i++) {
x >>>= 1; //Logical shift by 1
}
return x;
}
4. Common Bit Methods
4.1 Getting Bit
Given an integer and a specific position, check whether the bit at this position of the given number is one.
boolean getBit(int num, int i) { // i range is {0, 31}, 0 is the rightest
return (num & (1 << i)) != 0; // if i = 4, (1 << i) => 00010000
}
4.2 Setting Bit
Given an integer and a specific position, set the bit at this position of the given number to one.
int setBit(int num, int i) {
return num | (1 << i); // if i = 4, (1 << i) => 00010000
}
4.3 Clearing Bit
Given an integer and a specific position, set the bit at this position of the given number to zero.
int clearBit(int num, int i) {
int mask = ~(1 << i); // if i = 4, (1 << i) => 00010000, mask = 11101111
return num & mask;
}
4.4 Clearing Bit(Left Part)
Given an integer and a specific position, clear all bits from the most significant bit through i (inclusive).
int clearBitsMSthroughI(int num, int i) {
int mask = (1 << i) - 1; // if i = 4, (1 << i) => 00010000, mask = 00001111
return num & mask;
}
4.5 Clearing Bit(Right Part)
Given an integer and a specific position, clear all bits from i (inclusive) through 0 (inclusive).
int clearBitsIthrough0(int num, int i) {
int mask = -1 << (i + 1); // if i = 4, mask = 11100000
return num & mask;
}
4.6 Updating Bit
Given an integer and a specific position, set the bit at this position of to a given value(0 or 1).
int updateBit(int num, int i, boolean bitIsOne) {
int value = bitIsOne ? 1 : 0;
int mask = ~(1 << i); // if i = 4, mask = 11101111
return (num & mask) | (value << i); // if i = 4, and value = 1, (value < i) = 00010000
}
4.7 Pairwise Swap
Given an integer, swap its odd and even bits with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, and so on).
int swapOddEvenBits(int num) { // solution based on 32-bit system
// a => 1010, 5 => 0101
return (((num & 0xaaaaaaaa) >>> 1) | ((num & 0x55555555) << 1));
}
5. Arithmetic Implementation
// It works for both positive as well as negative numbers
public int add(int a, int b) {
while (b != 0) {
int c = a & b; // Find the carry bits
a = a ^ b; // Add the bits without considering the carry
b = c << 1; // Propagate the carry
}
return a;
}
public int sub(int a, int b) {
return add(a, -b);
}
public int multiply(int a, int b) {
todo
}
public int divide(int a, int b) {
todo
}
5.1 Checking If An Integer is Power of Two.
n & (n-1) == 0;
Example: If n = 8, then 1000 & 111 == 0 If n = 9, then 1001 & 1000 == 1000 != 0 If n = 10, then 1010 & 1001 == 1000 != 0
5.2 Getting the last 1 for a number
Or we can say find the biggest factor with power of two for number x.
x &= -x;
Examples: if x = 5, then x = 0101 & (1011) = 0001 = 1 = 2^0 if x = 6, then x = 0110 & (1010) = 0010 = 2 = 2^1 if x = 28, then x = 00011100 & 11100100 = 00000100 = 4 = 2^2
5.2 Implementing mathematic addition
int add(int a, int b) {
while (b != 0) {
int c = a & b; // Find the carry bits
a = a ^ b; // Add the bits without considering the carry
b = c << 1; // Propagate the carry
}
return a;
}
The code shown above is actually the way how we calculate sum of two numbers in decimal. For example: a = 138, b = 296 Step 1: Calculate sum of two number without taking the carry, 138 + 296 = 324 Step 2: Calculate sum of two number by only getting the carry, 138 + 296 = 011 Step 3: Shift the carry result to left by 1 then add sum1, 0324 + 0110 = 434.
6. Decimal to Binary
2147483647 = 011111111111111111111111111111111
3 = 000000000000000000000000000000011
2 = 000000000000000000000000000000010
1 = 000000000000000000000000000000001
0 = 000000000000000000000000000000000
-1 = 111111111111111111111111111111111
-2 = 111111111111111111111111111111110
-3 = 111111111111111111111111111111101
-2147483647 = 100000000000000000000000000000001
-2147483648 = 100000000000000000000000000000000