Efficient way to find Next Smaller number with same number of 1 bits

Question

I'm working on this question and come up with a solution (May be one or two condition needs to be added) but not sure if this is the right way to do it and find it cumbersome to use two loops and not sure if this is the efficient way of doing it. It would be great if anyone has some nice trick to do it or any better approach would be welcome :). (Language is not a barrier)

My Algorithm:

• First find the first '0' lsb bit in the number
• then find the next set bit which is next to this '0' bit
• Change the one you find '0' bit to 1 & '1' bit to '0'
• The number you'll get is next smaller
• if all the bit is set then you don't have any number which is next smaller with the same number of '1' bits.

void nextSmaller(int number) {
    int firstZeroBitHelper = 1, nextOneBitHelper;
    while (firstZeroBitHelper < number) {
        // when we find first lsb zero bit we'll stop
        bool bit = number & firstZeroBitHelper;
        if (bit == false)
            break;
        firstZeroBitHelper = firstZeroBitHelper << 1;
    }

    if (firstZeroBitHelper >= number) {
        cout << "No minimum number exists" << endl;
        return;
    }

    nextOneBitHelper = firstZeroBitHelper;
    nextOneBitHelper = nextOneBitHelper << 1;

    while (nextOneBitHelper < number) {
        // when we get '1' after the previous zero we stop
        bool bit = number & nextOneBitHelper;
        if (bit == true)
            break;
        nextOneBitHelper = nextOneBitHelper << 1;
    }

    // change the first zero to 1
    number = number | firstZeroBitHelper;
    // change the next set bit to zero
    number = number & ~nextOneBitHelper;

    cout << number << endl;
}

Answer 1

If you have an efficient next larger version then the simple (and only a couple of operation longer) version is to use a linear transform to map/unmap the input/output:

// example next larger integer with the same popcount as 'x'
uint64_t pop_next(uint64_t x)
{
  uint64_t t = x + (x & -x);
  x = x & ~t;
  x = x >> ctz(x) & 0x3f;  // see below
  x = x >> 1;
  return t^x;
}

// next smaller integer with same popcount as 'x'
uint64_t pop_prev(uint64_t x)
{
  return ~pop_next(~x); 
}

notes:

• ctz counts the number of trailing zeros.
• the AND mask following the ctz is to prevent undefined behavior (UB) in C/C++ in the case where the input is zero (then ctz(0) = 64 and the shift is UB)
• the second shift is likewise to prevent UB (instead of adding one to ctz) and doesn't hurt anyway (Intel trading an add for a shift and ARM can do both shifts in one op).

FWIW: I wrote a detailed version here.

Answer 2

#include <iostream>

bool AlmostdivBy2(int num) {
    return (-~num & (num)) == 0;
}

void toggleright(int &num) {
    int t;
    for (t = -1; num & 1; t++)
        num >>= 1;
    ++num = (num << t) | ~-(1 << t);
}

void toggleleft(int &num) {
    while (~num & 1)
        num >>= 1; //Simply keep chopping off zeros
    //~num & 1 checks if the number is even
    //Even numbers have a zero at bit at the rightmost spot
}

int main() {

    int value;
    std::cin >> value;
    if (!AlmostdivBy2(value)) {
        (~value & 1) ? toggleleft(value) : toggleright(value);
    }
    std::cout << value << "\n";
    return 0;
}

I think I might have over thought this one, but here is my explanation:

• If the number is close to being a power of 2 i.e values like 1, 3, 7, 15, 31, ..., then there is no value smaller than it that could have the same number of ones in their binary representation. Therefore we don't worry about these numbers.

• if the number is even, that is another easy fix, we simply keep chopping off zeros from the end until the number is odd

• Odd numbers presented the most challange which is why it is recursive. First you had to find the first zero bit starting from the right of the number. When this is found, you add one to that number which will turn that last bit to a 1. As the recursion unwinds you keep shifting the bits to the left and adding one. When this is done, you have the next smallest.

Hope I didn't confuse you

EDIT

Worked on it more and here is a non recursive version of toggleright

void toggleright(int &num) {    
    int t = 1;
    while ( (num >>= 1) & 1 && t++ );
    num = (-~num << ~-t) | ~-(1 << t);    
}

Answer 3

Going upwards:

• Find the rightmost occurrence of "01" in the number and make it "10".
• Justify all following 1-bits as far to the right as possible.

Going downwards:

• Find the rightmost occurrence of "10" in the number and make it "01".
• Left-justify all following 1-bits (i.e. don't do anything if the bit you just set is already followed by a 1).

An example to make the downwards case clear:

• 225 = 0b11100001
• Swap: 0b11010001
• Left-justify: 0b11011000 = 216

I'll explain the case of going upwards first, because it feels less tricky to me. We want to find the least-significant position where we can move a 1-bit one position left (in other words, the rightmost 0 that has a 1 to its right). It should be clear that this is the rightmost bit that we can possibly set, since we need to clear a bit somewhere else for every bit we set, and we need to clear a bit somewhere to the right of the bit we set, or else the number will get smaller instead of larger.

Now that we've set this bit, we want to clear one bit (to restore the total number of set bits), and reshuffle the remaining bits so that the number is as small as possible (this makes it the next greatest number with the same number of set bits). We can clear the bit to the right of the one we just set, and we can push any remaining 1-bits as far right as possible without fear of going below our original number, since all the less-significant bits together still add up to less than the single bit we just set.

Finding the next lower number instead of the next higher is basically the same, except that we're looking for the rightmost position where we can move a set bit one position right, and after doing that we want to move all less-significant bits as far left as possible.

It looks like others have got the bit-twiddling versions of this well in hand, but I wanted to see if I could give a good explanation of the logical/mathematical side of the algorithm.

Answer 4

Continuing from my comment..

Well, I found it, and pretty quickly too. See The Art of Computer Programming chapter 7.1.3 (in volume 4A), answer to question 21: "the reverse of Gosper's hack".

It looks like this:

t = y + 1;
u = t ^ y;
v = t & y;
x = v - (v & -v) / (u + 1);

Where y is the input and x the result. The same optimizations as in Gosper's hack apply to that division.

Answer 5

anatolyg covered your algorithm pretty well, but there's a more efficient solution.

You can use Gosper's hack with a clever realization that if you flip the bits around, then Gosper's produces the values in descending order.

Something like this pseudocode would work:

let k := number
let n := num bits in k (log base 2)
k = k ^ ((1 << n) - 1)
k = gosper(k)
k = k ^ ((1 << n) - 1)
return k

This gives you a nice O(1) (or O(log n) if you consider xor to be linear time) algorithm. :)

There are some cases you have to consider, like if k=2^x-1 for some x, but that's pretty easy to catch.

Answer 6

The algorithm you described is not quite correct; it does everything right except one detail. Any binary number has the following form, found in the middle of your algorithm:

xxxxx...10000...1111...
         ---n---// f // 

Here xxx... are arbitrary bits, and the numbers of consecutive zeros and ones are determined by firstZeroBitHelper and nextOneBitHelper (f and n).

Now you have to decrease this number leaving the same number of set bits, which necessarily turns the most significant 1 to 0:

xxxxx...0????...????...
         -----n+f------ 

Note that any value for bits ??? makes the new number less than the original one, and you really want to choose these bits such that the resulting number has maximal value:

xxxxx...011111...0000...
         ---f+1--//n-1// 

So you have to flip not just 2 bits, but f+2 bits (one bit from 1 to 0, and f+1 others from 0 to 1).

One way to do that is as follows.

First turn off all relevant bits:

number &= ~nextOneBitHelper;
number &= ~(nextOneBitHelper - 1);

Now turn on the needed bits, starting from MSB:

nextOneBitHelper >>= 1;
while (firstZeroBitHelper != 0)
{
    number |= nextOneBitHelper;
    nextOneBitHelper >>= 1;
    firstZeroBitHelper >>= 1;
}

It is possible to implement the bit twiddling described above without loops; for that you would need to calculate n and f. Having done that:

unsigned mask = (1 << (f + 1)) - 1; // has f+1 bits set to 1
mask <<= n - 1; // now has these bits at correct positions
number |= mask; // now the number has these bits set