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

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]
        (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

  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

    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 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);
    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;
    }
    }

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: