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.
Programming Praxis 
Cool drill. Here is my take on it, using Julia.
function FindWeight(x::Int64)
X = bin(x)
c = 0
end
function main(x::Int64)
z = x + 1
w = FindWeight(x)
end
main(7) # outputs 11
main(1) # outputs 2
main(100) # outputs 104
Have a nice weekend everyone!
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";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.
@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.
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;
}
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] (let [next-bit-mask (bit-shift-left bit-mask 1)] (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 (bit-or next-bit-mask lsbits) (if (= (bit-and i next-bit-mask) 0) (bit-or next-bit-mask (bit-and i (bit-not bit-mask))) (recur next-bit-mask (bit-or (bit-shift-left lsbits 1) 1)))) (recur next-bit-mask lsbits)))))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
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:
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; }Here’s a port to Python, which works on arbitrary sized integers.
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); }A Haskell version.
{-# 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 mOops. 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.
@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.
@Globules: and using popcount (which these days will be a single instruction) is a nice optimization over the original.
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:
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)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)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)[…] a comment on the prior exercise, Richard A. O’Keefe […]
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);
number |= mask;
}
}
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;
}
}
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();
}
}
By the way, Rust has a function that does this call count_ones()
A couple of solutions in Racket.