Bit Operations DSA

Bit Operations DSA | In Bitwise Operator we discussed the bitwise operations in detail. Here we will see some questions on it, and discuss the following algorithms:- Brian Kerningam’s Algorithm.

Table of Contents

• Java Pre-defined Methods for Number to Binary Conversion and Vice-versa
• Left (<<) and Right (>>) Shift Operator
• Check If the kth bit is Set
• Count set bits in Integer (Hamming weight)
  • Brian Kerningam’s Algorithm
  • Lookup Table Method for 32-bit Numbers
• Count Set Bit in Numbers 1 to N
• Power of Two
• Find the Only odd-occurring Numbers
• Find Missing Number in Array [1 to n+1]
• Find Two Odd Appearing Numbers
• Generating Power set using Bitwise operator
• Sparse Number

---

Java Pre-defined Methods for Number to Binary Conversion and Vice-versa

// decimal to binary
int decimal = 8;
String binaryString = Integer.toBinaryString(decimal);
System.out.println(binaryString); // Output: 1000

// binary to decimal
String binaryString = "1000";
int decimal = Integer.parseInt(binaryString, 2);
System.out.println(decimal); // Output: 8

Left (<<) and Right (>>) Shift Operator

Left Shift (<<)

• Operation: Shifts the bits of a number to the left by a specified number of positions.
• Effect: Each left shift effectively multiplies the number by 2.

int a = 5; // Binary: 0000 0101
int result = a << 1; // Shifts bits to the left by 1 position, result: 0000 1010 (10)

Right Shift (>>)

• Operation: Shifts the bits of a number to the right by a specified number of positions.
• Effect: Each right shift effectively divides the number by 2, and retains the sign bit (i.e., it keeps the number’s positive or negative sign).

int a = 10; // Binary: 0000 1010
int result = a >> 1; // Shifts bits to the right by 1 position, result: 0000 0101 (5)

Unsigned Right Shift (>>>)

• Operation: Shifts the bits of a number to the right by a specified number of positions, but fills the leftmost bits with zeros, regardless of the sign.

int a = -10; // Binary: 1111 0110 (in 8-bit representation)
int result = a >>> 1; // Shifts bits to the right by 1 position, result: 0111 1011 (Unsigned shift)

Mnemonics to Remember:

1. Left Shift (<<): Think “Left Multiplies” – Shifting left increases the number’s value by multiplying by 2 for each shift.
2. Right Shift (>>): Think “Right Divides” – Shifting right decreases the number’s value by dividing by 2 for each shift.
3. Unsigned Right Shift (>>>): Remember that it’s like the right shift but it doesn’t care about the sign, just moves the bits and fills in with zeros.

Quick Tips:

• For positive numbers: >> and >>> give the same result.
• For negative numbers: >>> fills the leftmost bits with zeros, which might not be intuitive, so remember it as the “unsigned shift.”

Check If the kth bit is Set

If N = 5, then convert it to binary form and check kth (from right side) digit is 1 or not. If it is 1 then it is set else not.

N=5, k=1; O/P: Yes
N=8, k=2; O/P: No
N=0, k=3; O/P: No

Method-1: Left Shift

public class Test {
    public static void main(String[] args) {
        int n = 5, k = 3;
        if ((n & (1 << (k - 1))) != 0) {
            System.out.println("yes");
        } else {
            System.out.println("no");
        }
    }
}

First n = 5 =”101″

1 << k-1 = 1 << 3-1 = 1 << 2 = 4 = "100"
   101
& 100 
=====
   100

Method-2: Right Shift

public class Test {
    public static void main(String[] args) {
        int n = 5, k = 3;
        if (((n >> (k - 1)) & 1) == 1) {
            System.out.println("yes");
        } else {
            System.out.println("no");
        }
    }
}

n = “101”; n >> (k-1) = “101” >> 2 = “1”

Count set bits in Integer (Hamming weight)

Set bits means 1. Count the number of 1’s in the binary representation of a given number. Problem: 191

N = 5; Number of set bits: 2
N = 7; Number of set bits: 3

Method-1: Naive solution

Use a count variable, remove the last bit from a given number, and check whether it is a set bit. If it is then increase the count variable.

public class Test {
    public static void main(String[] args) {
        int n = 13;
        int count = 0;
        while (n > 0) {
            if (n % 2 != 0) {
                count++;
            }
            n = n / 2;
        }
        System.out.println(count);
    }
}

Using bits it can be written as:-

if ((n & 1) == 1) {
    count++;
}
n >>= 2;

Or, simplified as:-

count += (n & 1);
n >>= 1;

Time complexity: O(Total bits in N)

Brian Kerningam’s Algorithm

Brian Kernighan’s Algorithm is a clever method used to count the number of set bits (1s) in the binary representation of an integer. The algorithm works by iteratively turning off the rightmost set bit of the number until the number becomes zero.

Time complexity: O(set bit count).

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

Example for N = 40.

n = 40 = 101000
n-1=39 = 100111
===============
100000 => n=32 (after n & (n-1)

n = 32 = 100000
n-1=31 = 011111
===============
000000 => 0 (after n & (n-1)

Lookup Table Method for 32-bit Numbers

Time complexity: θ(1), however, it requires some pre-processing. The Lookup table method is an efficient way to count the number of set bits (1s) in a 32-bit integer. This method uses a precomputed table to quickly determine the number of set bits in smaller chunks of the integer.

Brian Kernighan’s Algorithm is super efficient for counting bits in a single number due to its simplicity and O(number of set bits) complexity. The dynamic programming approach is indeed great for counting bits from 1 to N because it leverages previously computed results for efficiency. The Lookup Table Method can be handy for quick lookups but doesn’t necessarily offer a significant advantage over these other techniques in most scenarios.

1. Create a table of size 256, and fill it in such a way that table[i] represents the set bits in number i.
2. Convert 32 bits into 4 chunks of 8 bits.

• n & 0xFF (first 8 bits)
• (n >> 8) & 0xFF (next 8 bits)
• (n >> 16) & 0xFF (next 8 bits)
• (n >> 24) & 0xFF (last 8 bits

1. Use the lookup table to get the number of set bits for each 8-bit chunk.
2. Sum these values to get the total number of set bits in the 32-bit integer.

public class Test {
    private static int[] table = new int[256];
    static {
        for (int i = 0; i < table.length; i++) {
            table[i] = (i & 1) + table[i / 2];
        }
    }

    public static void main(String[] args) {
        int n = 40;
        int count = table[n & 0xFF];
        n = n >> 8;
        count += table[n & 0xFF];
        n = n >> 8;
        count += table[n & 0xFF];
        n = n >> 8;
        count += table[n & 0xFF];
        System.out.println(count);
    }
}

In short, it can be written as:-

int n = 40;
int count = table[n & 0xFF] + 
        table[n >> 8 & 0xFF] + 
        table[n >> 16 & 0xFF] + 
        table[n >> 24 & 0xFF];
System.out.println(count);

The notation 0xFF represents a hexadecimal (base 16) number. In hexadecimal, the digits range from 0 to 9 and A to F, where A stands for 10, B for 11, C for 12, D for 13, E for 14, and F for 15.

Count Set Bit in Numbers 1 to N

Given a non-negative integer N, write a function to count the number of set bits (1s) in the binary representation of all numbers from 1 to N. The function should return an array where each element i represents the number of set bits in the binary representation of the integer i.

Example: Input: N = 5 Output: [0, 1, 1, 2, 1, 2]

Explanation:-

• 0 in binary is 0 -> 0 set bits.
• 1 in binary is 1 -> 1 set bit.
• 2 in binary is 10 -> 1 set bit.
• 3 in binary is 11 -> 2 set bits.
• 4 in binary is 100 -> 1 set bit.
• 5 in binary is 101 -> 2 set bits.

We can use dynamic programming with Bit Manipulation. See more here:- Solution

import java.util.Arrays;

public class Test {
    public static int[] countBits(int n) {
        int[] dp = new int[n + 1];
        int offset = 1;
        for (int i = 1; i <= n; i++) {
            if (offset * 2 == i) {
                offset = i;
            }
            dp[i] = 1 + dp[i - offset];
        }
        return dp;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(countBits(2)));
    }
}

Time and space complexity O(n).

Power of Two

Check whether the number is a power of 2 or not. Problem: 231. Example:-
N=4; Yes
N=6; No
N=-8; No

Unset the only set bits and if the result becomes zero then the number is a power of 2. Negative numbers can not be the power of 2.

private static boolean isPowerOfTwo(int n) {
   if(n <= 0) {
       return false;
   }
   return (n & (n - 1)) == 0;
}

It can also written as:- return (n > 0) && (n & (n - 1)) == 0;

Example:- n=8 => 1000
n-1 = 7 => 111
1000 & 111 = 0

Find the Only odd-occurring Numbers

We have an array. In an array, there is only one element that occurred the odd number of times, remaining other occurred an even number of times. Find that odd occurring number. Problem: 136

Array = {4, 3, 4, 4, 4, 5, 5}; Output: 3

If we do XOR of a number with itself then it returns 0.
n = 5; n ^ n = 0;

Hence the idea is to iterate the array, XOR each element. Elements that occur even number of times will get canceled (0) with each other.

public class Test {
    public static void main(String[] args) {
        int[] arr = { 4, 3, 4, 4, 4, 5, 5 };
        int oddOcc = 0;
        for (int n : arr) {
            oddOcc ^= n;
        }
        System.out.println(oddOcc);
    }
}

Find Missing Number in Array [1 to n+1]

Given an array of N number that has values in the range [1 .. n]. Every number appears exactly once. Hence one number is missing. Find the missing number. Problem: 268

Array = {1, 4, 3}; Missing number: 2
Array = {1, 5, 3, 2}; Missing number: 4

To solve this, use another array from 1 to n, and XOR these array elements with the given array. Since the existing number will appear two times they will get canceled with each other whereas the missing number will remain as it is. Instead of creating a new array, we can also directly XOR the “i” of the for loop.

public class Test {
    public static void main(String[] args) {
        int[] arr = { 1, 4, 3 };

        int xor1 = 0;
        int xor2 = 0;

        for (int n : arr) {
            xor1 ^= n;
        }

        // 1 to n+1 (both inclusive)
        for (int i = 1; i <= arr.length + 1; i++) {
            xor2 ^= i;
        }

        System.out.println(xor1 ^ xor2);
    }
}

Time Complexity: O(n), Space Complexity: O(1)

We can solve it in another way by calculating the sum of natural numbers till n = n * (n+1) / 2.

int[] arr = { 1, 4, 3 };
int expectedSum = (arr.length + 1) * (arr.length + 2) / 2;

// sum of all array elements
int actualSum = Arrays.stream(arr).sum();
System.out.println(expectedSum - actualSum);

Time Complexity: O(n), Space Complexity: O(1)

Find Two Odd Appearing Numbers

In a given array there are two numbers which appear odd number of times, and all other elements appear even number of times. Find the numbers which appear odd number of times. Problem: 260

Array = {3, 4, 3, 4, 5, 4, 4, 6, 7, 7}; O/P: 5, 6
Array = {20, 15, 20, 17, 15, 15}; O/P: 15 17
Array = {3, 4, 3, 4, 8, 4, 4, 32, 7, 7}; O/P: 8 32

Steps:-

• XOR All Numbers: Find the XOR of all elements. This will give the XOR of the two numbers appearing an odd number of times (since all others cancel out).
• Find Rightmost Set Bit: Identify the rightmost set bit in the resultant XOR. This bit differs in the two numbers.
• Segregate Numbers: Partition the array into two groups based on whether the rightmost set bit is set or not.
• XOR Each Group: XOR all numbers within each group to find the two odd-occurring numbers.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        int[] arr = { 3, 4, 3, 4, 5, 4, 4, 6, 7, 7 };
        int[] arr1 = { 20, 15, 20, 17, 15, 15 };
        int[] arr2 = { 3, 4, 3, 4, 8, 4, 4, 32, 7, 7 };
        System.out.println(Arrays.toString(findMissingNumbers(arr)));
    }

    private static int[] findMissingNumbers(int[] arr) {
        int xor = 0, res1 = 0, res2 = 0;
        for (int k : arr) {
            xor ^= k;
        }
        int sn = xor & -xor;
        for (int k : arr) {
            if ((sn & k) != 0) {
                res1 ^= k;
            } else {
                res2 ^= k;
            }
        }
        return new int[] { res1, res2 };
    }
}

Different ways of finding the rightmost set bit:-

int sn = xor & -xor;
int sn = xor & ~(xor - 1);
int sn = Integer.lowestOneBit(xor);

To demonstrate we can add the following:-

private static int[] findMissingNumbers(int[] arr) {
    int xor = 0, res1 = 0, res2 = 0;

    // Calculate XOR of all elements in the array
    for (int n : arr) {
        xor ^= n;
    }

    List<Integer> group1 = new ArrayList<>();
    List<Integer> group2 = new ArrayList<>();

    // Find rightmost set bit in xor
    int sn = xor & ~(xor - 1);
    System.out.println("Rightmost digit: " + sn);

    // Divide elements into two groups based on the rightmost set bit
    for (int k : arr) {
        if ((k & sn) != 0) {
            res1 ^= k;
            group1.add(k);
        } else {
            group2.add(k);
            res2 ^= k;
        }
    }

    // Print groups for debugging
    System.out.println("Group1: " + group1);
    System.out.println("Group2: " + group2);

    // Return the two numbers that appear odd number of times
    return new int[]{res1, res2};
}

How it works:-

• XOR all numbers, and at the end XOR = 5 ^ 6 = 3
• Find the Rightmost Set Bit of 3 (binary: 0011). sn = xor & ~(xor – 1) = 3 & ~(2) = 3 & 1 = 1
• Segregate Numbers:-
  • Use the rightmost set bit to partition the array into two groups.
  • Group 1 (where the rightmost bit is set): 3, 3, 5, 7, 7 (bits: 0011, 0011, 0101, 0111, 0111).
  • Group 2 (where the rightmost bit is not set): 4, 4, 4, 4, 6 (bits: 0100, 0100, 0100, 0100, 0110).
• XOR Each Group:
  • Calculate XOR for each group.
  • Group 1: 3 ^ 3 ^ 5 ^ 7 ^ 7 = 5 (because pairs cancel out).
  • Group 2: 4 ^ 4 ^ 4 ^ 4 ^ 6 = 6 (because pairs cancel out).
  • The two numbers appearing an odd number of times are 5 and 6.

Another example:- {2, 4, 2, 6, 6, 8, 8, 8, 8, 8}.

• XOR = 2 ^ 4 ^ 2 ^ 6 ^ 6 ^ 8 ^ 8 ^ 8 ^ 8 ^ 8 = 4
• Rightmost set bit = sn = xor & ~(xor – 1) = 4 & ~(3) = 4 & 4 = 4
• Group 1 (where the rightmost bit is set): {4}
• Group 2 (where the rightmost bit is not set): {2, 2, 6, 6, 8, 8, 8, 8, 8}
• Group 1: 4 ^ 4 = 4.
• Group 2: 2 ^ 2 ^ 6 ^ 6 ^ 8 ^ 8 ^ 8 ^ 8 ^ 8 = 8.

Generating Power set using Bitwise operator

Given a string that represents a character set, generate all subsets of the given string. Problem: 78

I/P: s = “abc”
O/P: “”, “a”, “b”, “c”, “ab”, “ac”, “bc”, “abc”

I/P: s = “ab”
O/P: “”, “a”, “b”, “ab”

In general, if the string contains n characters then total subsets = 2^n.

Count (Decimal)	Counter (Binary)	Subset
0	000
1	001	a
2	010	b
3	011	a, b
4	100	c
5	101	a, c
6	110	b, c
7	111	a, b, c

public class Test {
    public static void main(String[] args) {
        String str = "ab";
        int powSize = (int) Math.pow(2, str.length());
        for (int counter = 0; counter < powSize; counter++) {
            for (int j = 0; j < str.length(); j++) {
                if ((counter & (1 << j)) != 0) {
                    System.out.print(str.charAt(j));
                }
            }
            System.out.println();
        }
    }
}

Counter & (1 << j) checks whether the jth bit is set (1) or not.

The time complexity for this code is O(n * 2^n). It is not the most efficient approach.

Sparse Number

A number is said to be a sparse number if no two or more consecutive bits are set in the binary representation. Write a program to check whether the given number is sparse or not.

To achieve the desired time complexity of O(1) and auxiliary space of (O(1)), we can use a bitwise operation to check if a number is sparse.

public class Test {
    public static void main(String[] args) {
        int number = 5; // Example number
        if (isSparse(number)) {
            System.out.println(number + " is a sparse number.");
        } else {
            System.out.println(number + " is not a sparse number.");
        }
    }

    private static boolean isSparse(int n) {
        // Right shift the number by one and then AND with the original number
        // If the result is 0, then it is sparse, otherwise not sparse
        return (n & (n >> 1)) == 0;
    }
}

The expression (n & (n >> 1)) checks if there are any consecutive set bits in the binary representation of n. If there are no consecutive set bits, the result of this expression will be 0, indicating that the number is sparse.

Understanding (n & (n >> 1)):-

• Right Shift (n >> 1): This operation shifts all bits of n to the right by one position. For example, if n = 6 (binary: 110), then n >> 1 results in 011 (which is 3).
• Bitwise AND (n & (n >> 1)): This operation performs a bitwise AND between n and n shifted right by one position.
• The bitwise AND results in 1 only if both bits are 1; otherwise, it results in 0.

n = 110
n >> 1 = 011
n & (n >> 1):
110 (original n)
011 (shifted n)
Result of AND = 010 (which is 2)

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Search