# 1203. Algorithm - Bit ManipulationXor and Shifting

Bit Manipulation.

• & (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) {
}

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