Next Identical Popcount, Revisited
June 26, 2018
We solved the next-permutation problem in a previous exercise, and it is easy to adapt that solution to the current task:
(define (next n) (undigits (reverse (next-perm < (reverse (cons 0 (digits n 2))))) 2))
Working from the inside out: we convert decimal to binary, cons a 0 onto the front (so there is a next permutation when all bits are 1), reverse (because that’s the order next-perm expects its arguments), call next-perm to advance to the next permutation, reverse (to put it back in the correct order, and convert back from a list of binary digits to a decimal number. Here are some examples:
> (next 15) 23 > (next 23) 27
And here’s the example O’Keefe gave:
> (time (next (expt 2 30)))
(time (next (expt 2 ...)))
no collections
0.000008361s elapsed cpu time
0.000006637s elapsed real time
2624 bytes allocated
2147483648
You can run the program at https://ideone.com/OcRmSv.
Programming Praxis 
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:
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: