Finding the Next Smallest & Largest Numbers with the Same Number of 1 Bits in Python

Introduction

In the realm of computer science and binary mathematics, a fascinating challenge is presented: Given an integer, can we find the next smallest and largest numbers that have the same number of 1 bit as the given number?

In this article, we will solve this problem using three distinct approaches: brute force, bit manipulation, and an arithmetic strategy. We will explore the logic and Python code behind each method, providing a comprehensive understanding of the problem-solving process.

Understanding the Problem

Before we dive into the solution, let’s break down the problem statement. Given an integer, we are tasked with finding two distinct integers that meet the following criteria:

Brute Force Approach

The Brute Force Approach is the easiest way to solve the given problem. Before moving to the Optimal Solution, let’s get a little intro with two Python Programs. These programs demonstrate the application of the Brute Force technique to determine the Next and Previous Numbers.

Brute Force Approach to Get the Next Number

The logic is quite straightforward. Examine the following steps:

Python Implementation

def countOnes(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count

def getNext(num):
    countGivenNum = countOnes(num)
    n = num
    while True:
        n += 1
        if countOnes(n) == countGivenNum:
            return n

if __name__ == "__main__":
    num = int(input("Please Enter the Number: "))
    nextNum = getNext(num)

    print("Next Largest Number: ", nextNum)

Output

Please Enter the Number: 8888
Next Largest Number:  8899

Brute Force Approach to Get the Previous Number

The approach’s logic closely resembles the previous one, with the only difference being that in this instance, we will decrease the provided number by one during Step 3.

Python Implementation

def countOnes(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count

def getPrevious(num):
    countGivenNum = countOnes(num)
    n = num
    while True:
        n -= 1
        if countOnes(n) == countGivenNum:
            return n

if __name__ == "__main__":
    num = int(input("Please Enter the Number: "))
    prevNum = getPrevious(num)

    print("Previous Largest Number: ", prevNum)

Output

Please Enter the Number: 8888
Previous Largest Number:  8884

Bit Manipulation Approach

Using bit manipulation, we can efficiently find the next smallest and largest numbers by changing the bits that maximize or minimize the value while maintaining the count of the set bits.

We will divide this discussion into two parts. The initial part will address obtaining the next number sharing the same count of 1 bits in its binary representation while the second part will focus on obtaining the previous number.

Bit Manipulation Approach to Get the Next Number

To understand the problem better, let’s consider the positive integer 12972 as an example. We want the next number with the same number of 1s.

Binary representation of the given number

Consider a number ‘n’, along with the positions of two bits, denoted as ‘i’ and ‘j’. If we invert the bit at position ‘i’ from 1 to 0 and the bit at position j from 0 to 1, the number ‘n’ will decrease if ‘i > j’. Conversely, if ‘i < j’, the number ‘n’ will increase.

Keep in Mind

1. If we flip a bit from zero to one, we must flip another bit from one to zero.

2. If we do that, the number will be bigger if and only if the zero-to-one bit is to the left of the one-to-zero bit.

3. We want the next larger number, not unnecessarily bigger.

See the following steps:

Step 1: Flip the rightmost non-trailing zero

In the above example, the rightmost trailing zeros are in the 0th and 1st position and the position of the rightmost non-trailing zero (zero followed by 1) is 4. We will call this position ‘p’.

Now we flip ‘p’ zero-to-one.

Flip the rightmost non-trailing zero

Following this change, the size of ‘n’ has been increased. Our subsequent task involves reducing the size of ‘n’. Prior to that, we will count ‘count0’ (number of zeroes after ‘p’) and ‘count1’ (number of ones after ‘p’).

Now we get: “count0=2“, “count1=2“, “p=4“.

Step 2: Clear bits to the right of ‘p’

At this step, we will reset all the bits (set to zero) situated to the right of ‘p’.

Clear all the bits to the right of ‘p’

Step 3: Add ‘count1 – 1’ number of ones (1s) on the right side

In the final stage, we should insert a total of ‘count1-1’ occurrences of ones (1s) at the extreme right position. Consequently, we will get the subsequent larger number compared to the given value n, while preserving an equal count of 1s in its binary representation.

Add the ‘count-1’ number of ones to the extreme right position

Python Implementation

def getNext(num):
    c = num
    count0 = 0
    count1 = 0

    # Computing count0: Number of zeros to the right of p
    while (((c & 1) == 0) and (c != 0)):
        count0 += 1
        c >>= 1
    # Computing count1: Number of ones to the right of p
    while ((c & 1) == 1):
        count1 += 1
        c >>= 1

    # If num == 11..1110...00, then there is no bigger 
    # number with the same number of 1s.
    if count0 + count1 == 31 or count0 + count1 == 0:
        return -1

    # Position of rightmost non-trailing zero
    p = count0 + count1

    # Flip the rightmost non-trailing zero
    num |= (1 << p)
    # Clear all bits to the right of p
    num &= ~((1 << p) - 1)
    # Insert (count1-1) ones(1s) on the right
    num |= (1 << (count1 - 1)) - 1

    return num

if __name__ == "__main__":
    num = int(input("Please Enter the Number: "))
    nextNum = getNext(num)

    print("Next Number: ", nextNum)

Output

Please Enter the Number: 12972
Next Number:  12977

Bit Manipulation Approach to Get Previous Number

In this scenario, the approach closely resembles the previous one, with a subtle distinction. Let’s consider a different number, 9607, as an example this time. Our objective is to determine the previous number that maintains the same count of 1s.

Consider the given number n, along with the positions of two bits, denoted as i and j. We perform a bit flip operation by changing the bit at position i from 1 to 0 and the bit at position j from 0 to 1. In this case, ‘i>j’.

See the following steps:

Step 1: Compute Initial Numbers

First, we need to compute ‘count1’ (number of trailing ‘1s’), ‘count0’ (size of the block of ‘0s’ just to the left of the trailing ‘1s’), and ‘p’ which is the rightmost non-trailing one (a ‘1’ followed by a ‘0’). We can get ‘p’ this way: “p = count0 + count1”.

The Binary representation of a positive integer number

According to the above example, we get “count1 = 3”, “count0 = 4”, and “p = 7”.

Step 2: Clear all the bits through ‘p’

After this operation, the binary representation will look like the following:

Clear all the bits through ‘p’

Step 3: Add the ‘count1 + 1’ number of ones just after to the right of ‘p’

After this step, we will get our desired result.

Add (count+1) number of ones just after the ‘p’

This is the previous number of the given integer, sharing an equivalent count of ‘1’ bits.

Python Implementation

def getPrev(num):
    c = num
    count0 = 0
    count1 = 0

    # Computing count1: Number of ones to the right of p
    while ((c & 1) == 1):
        count1 += 1
        c >>= 1

    if c == 0:
        return -1

    # Computing count0: Number of zeros to the right of p
    while (((c & 1) == 0) and (c != 0)):
        count0 += 1
        c >>= 1

    # Position of rightmost non-trailing one
    p = count0 + count1

    # Clear all bits to the right of p
    num &= ((~0) << (p + 1))
    # Sequence of (coun1+1) ones
    mask = (1 << (count1 + 1)) - 1
   
    num |= mask << (count0 - 1)

    return num

if __name__ == "__main__":
    num = int(input("Please Enter the Number: "))
    prevNum = getPrev(num)

    print("Previous Number: ", prevNum)

Output

Please Enter the Number: 9607
Previous Number:  9592

Arithmetic Approach

In this section, we will solve the same challenge utilizing arithmetic techniques. Similar to the Bit Manipulation approach, we will develop two distinct programs here: one to determine the next number and another to find the previous number.

Arithmetic Method to Get the Next Number

Remember the steps we followed in the bit manipulation approach to get the bigger number. An overview of these steps is presented below:

Step 1: Set the rightmost non-trailing zero (or ‘p’) to 1.

Step 2: Clear all the bits to the right of the ‘p’.

Step 3: Add (‘count1-1’) number of ones (1s) at the extreme right position.

All the above steps can be performed using an alternative way.

A quick way to accomplish Step 1 and Step 2 involves converting trailing zeros to ones and subsequently incrementing the number by 1 (or adding 1 to the number).

Let’s grasp this concept by looking at the following example:

Assume, n=1010101100. We set trailing zeros to 1. Now, n=1010101111.

Next, we increment the number ‘n’ by 1 (‘n+1’). Now, n=1010110000.

We can execute these two steps using arithmetic methods in the following way:

n = n + (2^count0) – 1    # Sets trailing 0s to 1, giving us ‘p’ trailing 1s.

n = n + 1    # Flips first ‘p’ 1s to 0s, and puts a 1 at the position of ‘p’.

Now, we do the following operation to perform Step 3 arithmetically.

n = n + (2^(count1-1)) – 1)    # Sets trailing (count1 – 1) zeros to ones (1s)

If we reduce the entire math, it would be like this,

nextNumber = n + ((2^count0) – 1) + 1 +  (2^(count1-1)) – 1)

“nextNumber =  n + (2^count0) +  (2^(count1-1)) – 1″

Python Implementation

def getNext(num):
    c = num
    count0 = 0
    count1 = 0

    # Computing count0: Number of zeros to the right of p
    while (((c & 1) == 0) and (c != 0)):
        count0 += 1
        c >>= 1
    # Computing count1: Number of ones to the right of p
    while ((c & 1) == 1):
        count1 += 1
        c >>= 1

    # If num == 11..1110...00, then there is no bigger 
    # number with the same number of 1s.
    if count0 + count1 == 31 or count0 + count1 == 0:
        return -1

    # Position of rightmost non-trailing zero
    p = count0 + count1

    return num + (1 << count0) + (1 << (count1 - 1)) - 1

if __name__ == "__main__":
    num = int(input("Please Enter the Number: "))
    nextNum = getNext(num)

    print("Next Number: ", nextNum)

Output

Please Enter the Number: 684
Next Number:  689

Arithmetic Method to Get Previous Number

If you remember the steps we followed in the bit manipulation approach to get the previous number, we took ‘count1’ as the number of trailing ones, ‘count0’ as the size of the block of zeros just to the left of the trailing ones, and p=count0+count1. Here, we will also keep the scenario as it is.

Now if we summarize the steps from there, it would be as follows:

Step 1: Set the bit at position ‘p’ to 0.

Step 2: Clear all the bits to the right of ‘p’.

Step 3: Add the ‘count1+1’ number of ones just to the right of ‘p’.

All these steps can be performed arithmetically also.

Assume, n=1010100011. According to this example, count1=2, count0=3.

Clear trailing ones. Now ‘n’ is 1010100000

Arithmetically: n = n – (2^count1) – 1

Flip trailing zeros. Now ‘n’ is 1010011111

Arithmetically: n = n – 1

Flip last ‘count0 – 1’ 1s. Now ‘n’ is 1010011100

Arithmetically: n = n – (2^(count0 – 1) – 1)

Simplifying the entire mathematical process yields a form similar to the one presented below:

prevNumber = n – ((2^count1) – 1) – 1 – (2^(count0 – 1) – 1)

“prevNumber = n – (2^count1) – (2^(count0 – 1)) + 1“

Python Implementation

def getPrev(num):
    c = num
    count0 = 0
    count1 = 0

    # Computing count1: Number of ones to the right of p
    while ((c & 1) == 1):
        count1 += 1
        c >>= 1

    if c == 0:
        return -1

    # Computing count0: Number of zeros to the right of p
    while (((c & 1) == 0) and (c != 0)):
        count0 += 1
        c >>= 1

    # Position of rightmost non-trailing one
    p = count0 + count1

    return num - (1 << count1) - (1 << ( count0 - 1)) + 1

if __name__ == "__main__":
    num = int(input("Please Enter the Number: "))
    prevNum = getPrev(num)

    print("Previous Number: ", prevNum)

Output

Please Enter the Number: 675
Previous Number:  668

Reference

Cracking the Coding Interview (Bit Manipulation, Problem #5.4) – Book by Gayle Laakmann McDowell

Summary

In this article, we explored three diverse approaches to solving the challenge of finding the next smallest and largest numbers with the same number of 1 bits as a given integer. The brute force method provides a basic solution, while the bit manipulation and arithmetic approaches offer more optimized and elegant solutions. Each approach highlights the power of understanding bitwise operations and mathematical patterns to efficiently solve binary-related problems.

By presenting these techniques and their corresponding Python implementations, this article equips you with the tools to tackle similar problems with confidence and creativity.