Find the next higher number containing the same number of set bits

Problem

Given a non-negative integer x, find the next higher integer that has the same number of set bits (1s) in its binary representation. If no higher integer exists (i.e., x is the largest permutation of its set bits), the behavior depends on application — typically iteration stops.

Examples

Example 1

Input: x = 0b01011100 (92)
Output: 0b01100011 (99)

Solution

This is a classic bit-fiddling trick that computes the next lexicographic bit permutation with the same popcount. The expression below produces the result in constant time for fixed-width unsigned integers:

a = x & -x
b = a + x
r = b | (((x ^ b) >> 2) / a)

Below we explain why this works and give a few implementations.

Method 1 — Bit trick using a = x & -x

Intuition

Isolate the rightmost set-bit run in x. The next higher number is produced by moving the rightmost contiguous block of 1s one position to the left and placing the remaining 1s in the lowest possible positions.

Approach

• If x == 0 return 0 or handle as sentinel.
• Let a = x & -x (isolates lowest set bit).
• Let b = x + a (clears the rightmost 1-run and sets the bit just left of it).
• Compute the low part c = ((x ^ b) >> 2) / a which right-adjusts the leftover ones into the low positions.
• Return r = b | c.

Edge cases:

• Use unsigned shifts and division; avoid signed arithmetic to prevent sign-extension.
• If b == 0 due to overflow (no higher permutation within word size), handle accordingly.

Code

C++

class Solution {
 public:
  unsigned int next_with_same_popcount(unsigned int x) {
    if (x == 0) return 0u;
    unsigned int a = x & -x;
    unsigned int b = x + a;
    unsigned int c = ((x ^ b) >> 2) / a;
    return b | c;
  }
};

Go

package main

func NextWithSamePopcount(x uint) uint {
    if x == 0 { return 0 }
    a := x & -x
    b := x + a
    c := ((x ^ b) >> 2) / a
    return b | c
}

Java

class Solution {
    public int nextWithSamePopcount(int x) {
        if (x == 0) return 0;
        int a = x & -x;
        int b = x + a;
        int c = ((x ^ b) >>> 2) / a; // unsigned shift
        return b | c;
    }
}

Python

class Solution:
    def next_with_same_popcount(self, x: int) -> int:
        if x == 0:
            return 0
        a = x & -x
        b = x + a
        c = ((x ^ b) >> 2) // a
        return b | c

Complexity

• ⏰ Time complexity: O(1) — a constant number of arithmetic/bit ops for fixed-width words.
• 🧺 Space complexity: O(1).

Method 2 — Next permutation style (algorithmic)

Intuition

Treat the bitstring as an array of bits and compute the next lexicographic permutation with the same number of 1s using a standard next-permutation approach: find the pivot (a 1 followed by a 0 to its left), swap, and right-adjust the suffix.

Approach

• Extract positions of set bits or scan from LSB to MSB to find the rightmost 01 pattern where swapping yields an increase.
• After swapping the 01 to 10, move all 1s to the rightmost positions of the suffix.

Code (sketch)

C++

unsigned int next_with_same_popcount_slow(unsigned int x) {
  if (x == 0) return 0u;
  unsigned int t = x;
  int pos = 0;
  // find first zero that has a one somewhere to its right
  while ((t & 1u) == 1u) { t >>= 1; pos++; }
  while ((t & 1u) == 0u) { t >>= 1; pos++; }
  // pos now points to the bit to flip
  unsigned int mask = (1u << pos) - 1u;
  unsigned int ones = x & mask;
  // clear lower bits and set the bit at pos
  unsigned int res = (x & ~mask) | (1u << pos);
  // place ones-1 in the lowest positions
  res |= (ones >> 1);
  return res;
}

Complexity

• ⏰ Time complexity: O(b) where b is word size — scanning bits.
• 🧺 Space complexity: O(1).

Notes & References

• This trick is useful for iterating over fixed-size subsets of a given cardinality.
• Source references are in source_links in frontmatter.