## Next Identical Popcount

### June 22, 2018

Today’s exercise is an interview question:

The binary weight of a positive integer is the number of 1-bits in its binary representation. For example, the decimal number 7, which is 111 in binary, has a binary weight of 3. The smallest integer greater than 7 that has the same binary weight as 7 is 11, which is 1011 in binary.

Your task is to write a program that, given a positive integer, finds the next larger integer that has the same binary weight. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 23 Responses to “Next Identical Popcount”

1. Zack said

Cool drill. Here is my take on it, using Julia.

function FindWeight(x::Int64)
X = bin(x)
c = 0

``````for digit in X
if digit == '1'; c += 1; end
end

return c
``````

end

function main(x::Int64)
z = x + 1
w = FindWeight(x)

``````while true
w_ = FindWeight(z)
if w_ == w; return z; end
z += 1
end
``````

end

main(7) # outputs 11
main(1) # outputs 2
main(100) # outputs 104

Have a nice weekend everyone!

2. ```sub bc{sprintf("%b",shift)=~tr/1/1/}
\$bc0=bc(\$v=shift);
for(\$v++;bc(\$v)-\$bc0;\$v++){}; ## write while loop as for loop;
print \$v,"\n";
```

or slightly longer – but without the sprintf “hack” to get the binary count using & / >> operator

```sub bc{\$r=0;\$t=shift;while(\$t){\$r+=\$t&1;\$t>>=1};return \$r;}
\$bc0=bc(\$v=shift);
for(\$v++;bc(\$v)!=\$bc0;\$v++){};
print \$v,"\n";
```
3. Richard A. O'Keefe said

This is just the “next k-subset of 1..n” problem. It is possible to go fairly directly from one popc-k integer to the next. Let the least significant 1
bit be at offset p. If bit(p+1) is 0, set it to 1 and clear bit(p). If bit(p+1)
is 1, clear bit(p), set bit(0), advance bits (p+1..msb) to the next integer
with k-1 bits.

The algorithm at the top of the page is spectacularly inefficient. Consider
the case of 32-bit integers, bit(30) is on, and all the others are off. (k=1)
The (next n) algorithm loops about 2**30 times.

4. Daniel said

@Richard_OKeefe, for 0b111000, the next number should be 0b1000011. I believe your proposed algorithm would incorrectly return 0b1010001. Please let me know if I’ve misinterpreted.

5. Assuming 32-bin unsigned integers and supporting wraparound:

unsigned int next_identical_popcount(unsigned int n) {
unsigned short shift = 0;
unsigned int ones = 0;
while (shift < 31) {
if ((n & 3) == 1)
return (((n + 1) << shift) | ones);
if ((n & 1) == 1)
ones = (ones << 1) | 1;
n >>= 1;
shift++;
}
if (n == 1)
ones = (ones << 1) | 1;
return ones;
}

6. sbocq said

Clojure/Script with arbitrary precision integer.

The solution scans each bit b of the input i consecutively using a bit mask b that it shifts left at each iteration. If i(b) is 1 and i(b+1) is 0, then it sets i(b) to 0 and i(b+1) to 1. If there are only contiguous 1’s until the msb, then it shifts left the msb by 1 and or’s it with the remaining bits kept in lsb position (lsbits).

```(defn next-weight [i]
(loop [bit-mask 1 lsbits 0]
(if (> (bit-and i bit-mask) 0)
(if (= (bit-and i (bit-not (bit-or (dec bit-mask) bit-mask))) 0) ; only contiguous 1's
(if (= (bit-and i next-bit-mask) 0)
(recur next-bit-mask (bit-or (bit-shift-left lsbits 1) 1))))
```

Test:
``` cljs.user=> (next-weight 7) 11 cljs.user=> (next-weight 15) 23 cljs.user=> (next-weight 23) 27 cljs.user=> (next-weight 56) 67 ```

7. Daniel said

Here’s a solution in C.

y has the rightmost bit of x. z has the rightmost group of bits from x turned off, and the neighbor bit to the left turned on. The output or’s z with x’s rightmost group of bits shifted to the right 1 place past the end (i.e., 1 bit truncated).

```#include <stdio.h>
#include <stdlib.h>

// next identical popcount
unsigned nip(unsigned x) {
unsigned y = x & (~x + 1);
unsigned z = x + y;
unsigned mask = (x ^ z) - 1;
return z | ((x & mask) / (y << 1));
}

int main(int argc, char* argv[]) {
if (argc != 2) {
fprintf(stderr, "Usage: %s UINT\n", argv[0]);
return EXIT_FAILURE;
}
unsigned x = strtoul(argv[1], NULL, 10);
printf("%u\n", nip(x));
return EXIT_SUCCESS;
}
```

Example:

```\$ ./nip 15
23

\$ ./nip 23
27
```
8. Daniel said

Here’s the same approach I posted above, but using GCC’s intrinsic __builtin_ffs to shift the group of 1s instead of division.

```#include <stdio.h>
#include <stdlib.h>

// next identical popcount
unsigned nip(unsigned x) {
unsigned y = x + (x & (~x + 1));
unsigned ffs = __builtin_ffs(x);
return y | ((x & ((x ^ y) - 1)) >> ffs);
}

int main(int argc, char* argv[]) {
if (argc != 2) {
fprintf(stderr, "Usage: %s UINT\n", argv[0]);
return EXIT_FAILURE;
}
unsigned x = strtoul(argv[1], NULL, 10);
printf("%u\n", nip(x));
return EXIT_SUCCESS;
}
```
9. Daniel said

Here’s a port to Python, which works on arbitrary sized integers.

```def nip(x):
y = x & (~x + 1)
z = x + y
mask = (x ^ z) - 1
return z | ((x & mask) // (y << 1))
```
10. Daniel said

My earlier code has a mistake. The mask was intended to be ~(x & z) – 1. Alternatively, a mask of x ^ z makes sense too.

Coincidentally the mask I used doesn’t affect the result, since relevant bit ends up getting removed in the next step (but I wasn’t intending for it to work this way).

Here are the updates.

```// next identical popcount
unsigned nip(unsigned x) {
unsigned y = x & (~x + 1);
unsigned z = x + y;
unsigned mask = ~(x & z) - 1;
return z | ((x & mask) / (y << 1));
}
```
```// next identical popcount (using GCC intrinsic)
unsigned nip(unsigned x) {
unsigned y = x + (x & (~x + 1));
unsigned ffs = __builtin_ffs(x);
return y | ((x & (~(x & z) - 1)) >> ffs);
}
```
```def nip(x):
y = x & (~x + 1)
z = x + y
mask = ~(x & z) - 1
return z | ((x & mask) // (y << 1))
```
11. Globules said

```{-# LANGUAGE BinaryLiterals #-}

import Data.Bits
import Data.Int (Int16, Int32)
import Data.Word (Word8)
import Text.Printf (PrintfArg, printf)

-- The next larger "snob" (same number of bits) for the argument.  If there is
-- no next value then return nothing (this includes 0).
--
-- This algorithm was described by Bill Gosper in the HAKMEM technical report.
nextSnob :: (Integral a, Bits a) => a -> Maybe a
nextSnob n = let s = n .&. negate n
r = s + n
in if r == 0 then Nothing
else Just \$ r .|. (1 `shiftL` (popCount (n `xor` r) - 2) - 1)

main :: IO ()
main = do
-- Works with signed and unsigned types, of both finite and arbitrary length.
demoF (0b00011010 :: Word8)
demoF (0b111001100010100 :: Int16)
demoF (0 :: Int32)
demoF (0b11100000 :: Word8)
demoI 0b110110011110001100100000101111111111111111111111111111111111111111111

---------------------------------- Utilities ----------------------------------

demoF :: (PrintfArg a, Integral a, FiniteBits a) => a -> IO ()
demoF n = demo (finiteBitSize n) n

demoI :: Integer -> IO ()
demoI = demo 0

demo :: (PrintfArg a, Integral a, Bits a) => Int -> a -> IO ()
demo w n = case nextSnob n of
Nothing -> printf "%0*b\n<no next snob>\n\n" w n
Just m  -> printf "%0*b\n%0*b\n\n" w n w m
```
```\$ ./nextsnob
00011010
00011100

0111001100010100
0111001100011000

00000000000000000000000000000000

11100000

110110011110001100100000101111111111111111111111111111111111111111111
110110011110001100100000110111111111111111111111111111111111111111111

```
12. Globules said

Oops. Shouldn’t have put those angle brackets in the “no next snob” string. Having removed them from the code, here’s what the output looks like.

```\$ ./nextsnob
00011010
00011100

0111001100010100
0111001100011000

00000000000000000000000000000000
no next snob

11100000
no next snob

110110011110001100100000101111111111111111111111111111111111111111111
110110011110001100100000110111111111111111111111111111111111111111111

```
13. matthew said

@Globules: I was about to say “this is in HAKMEM!”, but you beat me to it. Link: http://home.pipeline.com/~hbaker1/hakmem/hacks.html#item175, I’d guess that is PDP-8 or 11 assembler.

14. matthew said

@Globules: and using popcount (which these days will be a single instruction) is a nice optimization over the original.

15. Kevin said

A solution in racket:

```(define (pop-count num)
(define (bin-weight n)
(foldl (lambda (c acc) (+ acc (if (equal? c #\1) 1 0)))
0
(string->list(number->string n 2))))
(let ((target (bin-weight num)))
(let get-pop-count ((n (add1 num)))
(if (= (bin-weight n) target) n (get-pop-count (add1 n))))))
```

Testing:

```(pop-count 1) ==> 2
(pop-count 7) ==> 11
(pop-count 10) ==> 12
(pop-count 100) ==> 104
(pop-count 65535) ==> 98303
```
16. Daniel said

Here’s a solution in Python that operates on a string representation of the binary number. It finds the last group of ones, then swaps a one from this group with the zero to the left, and moves the remaining ones to the end.

```def nip(x):
s = bin(x)[2:]
groups = [list(g) for _, g in groupby(s)]
post = groups.pop() if s.endswith("0") else []
ones = groups.pop()
pre = groups.pop() if groups else ["0"]
groups.append(pre[:-1])
groups.append(['1', '0'])
groups.append(post)
groups.append(ones[:-1])
return int("".join(["".join(g) for g in groups]), 2)
```
17. Daniel said

I forgot the import.

```from itertools import groupby

def nip(x):
s = bin(x)[2:]
groups = [list(g) for _, g in groupby(s)]
post = groups.pop() if s.endswith("0") else []
ones = groups.pop()
pre = groups.pop() if groups else ["0"]
groups.append(pre[:-1])
groups.append(['1', '0'])
groups.append(post)
groups.append(ones[:-1])
return int("".join(["".join(g) for g in groups]), 2)
```
18. Paul said

In Python.

```from itertools import count

def popcount(n):
"""find the number of 1's in bin(n)"""
c = 0
while n:
n &= n - 1
c += 1
return c

def bf(n):
"""next identical number with same popcount as n - brute force"""
pn = popcount(n)
for m in count(n+1):
if popcount(m) == pn:
return m

def nip(n):
"""next identical number with same popcount as n"""
b = "0" + bin(n)[2:]   # add 0 to make sure 01 combination is found
L = len(b)
i = b.rindex("01")
# swap 01 at location i and
# shift all 1's starting at location i+2 to the right
j = i + 2
Lj = L - j
ones = b.count("1", j)
b = b[:i] + "10" + "0" * (Lj - ones) + "1" * ones
return int(b, 2)
```
19. […] a comment on the prior exercise, Richard A. O’Keefe […]

20. Tom Parrish said

A solution in C#, for Linqpad.

void Main()
{
CalculateNextIdenticalPopcount(5);
CalculateNextIdenticalPopcount(7);
CalculateNextIdenticalPopcount(21);
}

int CalculateNextIdenticalPopcount(int input)
{
var bits = input.GetBits(out var bitCount);
var binaryWeight = bits.Count(b => b);
var successorBits = new bool[bitCount+1];
successorBits[bitCount] = true;
for(int i=0;i<binaryWeight-1;i++)
{
successorBits[i] = true;
}
var successor = successorBits.ToInt32();
\$"{FormatNumber(input)} => {FormatNumber(successor)}".Dump();

return successor;
}

string FormatNumber(int number)
{
var bits = number.GetBits(out var bitCount);

var builder = new StringBuilder();
builder.Append(number);
builder.Append(" (");
for(int i=bitCount-1;i>=0;i–)
{
builder.Append(bits[i] ? 1 : 0);
}
builder.Append(")");

return builder.ToString();
}

static class BitExtensions
{
public static Int32 ToInt32(this bool[] bits)
{
Int32 number = 0;
for (int i = 0; i < bits.Length; i++)
{
if(bits[i])
{
var mask = (1 << i);
}
}
return number;
}

public static bool[] GetBits(this Int32 number, out int bitCount)
{
var integerBits = sizeof(Int32) * 8;
var bits = new bool[integerBits];
bitCount = 0;
for (int i = 0; i < integerBits; i++)
{
var mask = (1 << i);
bits[i] = (mask & number) == 0 ? false : true;
if(bits[i])
{
bitCount = i+1;
}
}

return bits;
}
}

21. amateur_coder said

import java.util.Scanner;
public class binary_weight
{ public int x=0;
public int bin_wt(int n)
{ int sum=0;
while(n!=0)
{
sum+=n%2;
n/=2;
}
return(sum);
}
void check()
{
Scanner in=new Scanner(System.in);
System.out.println(“Enter the number”);
x=in.nextInt();
for(int i=x+1;i>0;i++)
{
if(bin_wt(x)==bin_wt(i))
{
System.out.println(“The number which has the same binary weight as ” +x+ ” is “+i); break;
}
else
continue;
}
}
public static void main(String args[])
{
binary_weight obj=new binary_weight();
obj.check();
}
}

22. By the way, Rust has a function that does this call count_ones()