Next Identical Popcount, Revisited

June 26, 2018

In a comment on the prior exercise, 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.

Dr. O’Keefe is correct. My solution isn’t very good. In fact, it’s abominable.

Your task is to write a program to solve the next-identical-popcount problem in the manner Professor O’Keefe suggests. 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

Posted by programmingpraxis
Filed in Exercises
2 Comments »

2 Responses to “Next Identical Popcount, Revisited”

  1. Kevin said
    June 26, 2018 at 1:14 PM

    racket/scheme:

    (define (pop-count num)
  (define (bin-weight n)
    (foldl (λ (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
  2. Daniel said
    June 29, 2018 at 7:49 PM

    I believe that there is a problem with the described algorithm.

    For example, for 0b111000, the next number should be 0b1000011, but the algorithm above would incorrectly return 0b1010001.

    The problem is in the recursive call: “advance bits (p+1..msb) to the next integer with k-1 bits”

    That should seemingly be “advance bits (1..msb) to the next integer with k-1 bits”

    Where “p+1” was modified to “1”, and indexing is relative to the recursive call input, not the original bit string.

    Here’s a solution in Python with the modification.

    def nip(x):
  bits = list(reversed(bin(x)[2:])) + ["0"]
  p = bits.index("1")
  z = 0
  while True:
    bits[p] = "0"
    if bits[p+1] == "0":
      bits[p+1] = "1"
      break
    else:
      bits[z] = "1"
      p += 1
      z += 1
  return int("".join(reversed(bits)), 2)

print(nip(15))
print(nip(23))

    Output:

    23
27

Leave a comment