Johnnn

Let's go

Find next greater number with same number of set bits

by · Published · Updated

The problem of finding the next greater number with the same number of set bits is an interesting challenge in computer programming. Given a positive integer, the goal is to find the smallest possible number greater than the given number that has the same number of set bits (i.e., 1s) in its binary representation. In this blog post, we will explore the algorithms to solve this problem and provide implementations in C, C++, Python, and Java. Let’s dive in!

Algorithm:
The problem can be solved using the following algorithm:

  1. Find the rightmost zero bit (p) that has a set bit (1) to its right. This can be done by iterating from the least significant bit (LSB) to the most significant bit (MSB) and checking for the pattern “01” in the binary representation.
  2. Set the bit at position p to 1.
  3. Count the number of set bits (1s) to the right of position p (count1).
  4. Count the number of unset bits (0s) to the right of position p (count0).
  5. Set the count1 rightmost bits to 1 starting from position p-1.
  6. Set the count0 bits starting from the rightmost position to 0.
  7. The resulting number is the next greater number with the same number of set bits.

Implementations:

  1. C:
#include <stdio.h>

int countSetBits(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);
        count++;
    }
    return count;
}

int findNextGreaterNumber(int n) {
    int count1 = countSetBits(n);
    int count0 = 0;
    int p = 0;

    while (((n >> p) & 3) != 1)
        p++;

    n |= (1 << p);
    count1--;
    count0 = p - count1;

    n &= ~((1 << p) - 1);
    n |= (1 << (count1 - 1)) - 1;

    return n;
}

int main() {
    int n = 10;
    int nextGreater = findNextGreaterNumber(n);

    printf("The next greater number with the same number of set bits as %d is: %dn", n, nextGreater);

    return 0;
}
  1. C++:
#include <iostream>

int countSetBits(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);
        count++;
    }
    return count;
}

int findNextGreaterNumber(int n) {
    int count1 = countSetBits(n);
    int count0 = 0;
    int p = 0;

    while (((n >> p) & 3) != 1)
        p++;

    n |= (1 << p);
    count1--;
    count0 = p - count1;

    n &= ~((1 << p) - 1);
    n |= (1 << (count1 - 1)) - 1;

    return n;
}

int main() {
    int n = 10;
    int nextGreater = findNextGreaterNumber(n);

    std::cout << "The next greater number with the same number of set bits as " << n << " is: " << nextGreater << std::endl;

    return 0;
}
  1. Python:
def count_set_bits(n):
    count = 0
    while n:
        n &= (n - 1)
        count += 1
    return count

def find_next_greater_number(n):
    count1 = count_set_bits(n)
    count0 = 0
    p = 0

    while ((n >> p) & 3) != 1:
        p += 1

    n |= (1 << p)
    count1 -= 1
    count0 = p - count1

    n &= ~((1 << p) - 1)
    n |= (1 << (count1 - 1)) - 1

    return n

n = 10
next_greater = find_next_greater_number(n)
print("The next greater number with the same number of set bits as", n, "is:", next_greater)
  1. Java:
public class NextGreaterNumber {
    public static int countSetBits(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }

    public static int findNextGreaterNumber(int n) {
        int count1 = countSetBits(n);
        int count0 = 0;
        int p = 0;

        while (((n >> p) & 3) != 1)
            p++;

        n |= (1 << p);
        count1--;
        count0 = p - count1;

        n &= ~((1 << p) - 1);
        n |= (1 << (count1 - 1)) - 1;

        return n;
    }

    public static void main(String[] args) {
        int n = 10;
        int nextGreater = findNextGreaterNumber(n);

        System.out.println("The next greater number with the same number of set bits as " + n + " is: " + nextGreater);
    }
}

Conclusion:
Finding the next greater number with the same number of set bits is an intriguing problem that can be solved using bitwise operations. By identifying the rightmost zero bit with a set bit to its right and performing the required bit manipulations, we can obtain the desired result efficiently. Implementations in C, C++, Python, and Java have been provided to demonstrate the algorithm. By understanding and utilizing this problem-solving technique, you will be equipped to tackle similar challenges involving bitwise operations.

You may also like...