## Next Identical Popcount

### June 22, 2018

Computing the binary weight of an integer is an operation known as *popcount*, which we studied in a previous exercise. Popcount is an important calculation in cryptography and in error-correcting codes, and well worth our time for a review. Given a function to compute the popcount of a positive integer, it is easy to find the next integer with the same popcount:

(define (next n) (let ((p (popcount n))) (do ((n (+ n 1) (+ n 1))) ((= (popcount n) p) n))))

You can use any of the `popcount`

functions from the previous exercise. Here are some examples:

> (next 15) 23 > (next 23) 27

You can run the program at https://ideone.com/0wV2nY, where you will also see our definition of `popcount`

that makes one loop for each 1-bit in the given integer.

Advertisements

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!

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

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).

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).

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.

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.

A Haskell version.

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.

@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:

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.

I forgot the import.

In Python.

[…] 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.