Bit Manipulation - (Theory)

Bit Manipulation in Java – Complete Notes

1. Check if the ith Bit is Set

boolean isSet = (num & (1 << i)) != 0;

Explanation:

• (1 << i) creates a mask with only the ith bit set.

• Bitwise AND (&) isolates that bit.

• Non-zero result means the bit is set.

2. Set the ith Bit

num = num | (1 << i);

Explanation:

• OR operation with 1 << i sets the ith bit to 1.

3. Clear the ith Bit

num = num & ~(1 << i);

Explanation:

• ~(1 << i) creates a mask with 0 at the ith position and 1s elsewhere.

• ANDing clears the ith bit.

4. Toggle the ith Bit

num = num ^ (1 << i);

Explanation:

• XOR flips the ith bit.

5. Get the ith Bit (Value: 0 or 1)

int bit = (num >> i) & 1;

Explanation:

• Right shift and mask with 1 to extract the bit at position i.

6. Count Number of Set Bits (Hamming Weight)

Method 1: Brian Kernighan’s Algorithm

int count = 0;
while (num > 0) {
    num &= (num - 1);
    count++;
}

Method 2: Built-in

int count = Integer.bitCount(num);

7. Check if a Number is Power of 2

boolean isPowerOf2 = (num > 0) && (num & (num - 1)) == 0;

Explanation:

• Powers of 2 have only one set bit.

8. Get Lowest Set Bit

int lowestSetBit = num & (-num);

Explanation:

• Isolates the rightmost set bit.

9. Remove Lowest Set Bit

num = num & (num - 1);

Explanation:

• Removes the rightmost 1.

10. Turn Off Rightmost Contiguous 1s

num = num & (num + 1);

11. Extract Rightmost 0-bit

int rightmostZero = ~num & (num + 1);

12. XOR from 1 to n

Brute Force

int xorN = 0;
for (int i = 1; i <= n; i++) xorN ^= i;

Optimized

int xorN = (n % 4 == 0) ? n : (n % 4 == 1) ? 1 : (n % 4 == 2) ? (n + 1) : 0;

13. Swap Two Numbers Without Temp Variable

a = a ^ b;
b = a ^ b;
a = a ^ b;

14. Find Unique Number (All Others Appear Twice)

int unique = 0;
for (int num : arr) unique ^= num;

15. Find Two Unique Numbers (Others Appear Twice)

int xorAll = 0;
for (int num : arr) xorAll ^= num;

int mask = xorAll & -xorAll;

int a = 0, b = 0;
for (int num : arr) {
    if ((num & mask) == 0) a ^= num;
    else b ^= num;
}

16. Reverse Bits of a 32-bit Integer

public int reverseBits(int n) {
    int res = 0;
    for (int i = 0; i < 32; i++) {
        res <<= 1;
        res |= (n & 1);
        n >>= 1;
    }
    return res;
}

17. Multiply by 2 (Left Shift)

num = num << 1;

18. Divide by 2 (Right Shift)

num = num >> 1;

19. Find log2(num) (Position of Highest Set Bit)

int log2 = 0;
while (num > 1) {
    num >>= 1;
    log2++;
}

20. Check if Number is Even or Odd

boolean isOdd = (num & 1) == 1;
boolean isEven = (num & 1) == 0;

21. Find Parity (Odd or Even Number of 1s)

int parity = 0;
while (num > 0) {
    parity ^= (num & 1);
    num >>= 1;
}

22. Find Maximum Subset XOR

int maxSubsetXOR(int[] set, int n) {
    int index = 0;

    for (int i = 31; i >= 0; i--) {
        int maxIndex = index;
        int maxEle = Integer.MIN_VALUE;

        for (int j = index; j < n; j++) {
            if ((set[j] & (1 << i)) != 0 && set[j] > maxEle) {
                maxEle = set[j];
                maxIndex = j;
            }
        }

        if (maxEle == Integer.MIN_VALUE) continue;

        int temp = set[index];
        set[index] = set[maxIndex];
        set[maxIndex] = temp;

        for (int j = 0; j < n; j++) {
            if (j != index && (set[j] & (1 << i)) != 0)
                set[j] ^= set[index];
        }
        index++;
    }

    int res = 0;
    for (int i = 0; i < n; i++)
        res ^= set[i];
    return res;
}

Additional Practice Patterns

• Find bitwise AND of all numbers from L to R

• Set bits in a number (popcount)

• Bitmasking on subsets:

for (int mask = 0; mask < (1 << n); mask++) {
    for (int j = 0; j < n; j++) {
        if ((mask & (1 << j)) != 0) {
            // jth bit is set → include element[j]
        }
    }
}