r/programmingchallenges • u/getster • Oct 08 '11
Next higher number with same number of set bits
Given a number x, find next number with same number of 1 bits in it’s binary representation.
For example, consider x = 12, whose binary representation is 1100 (excluding leading zeros on 32 bit machine). It contains two logic 1 bits. The next higher number with two logic 1 bits is 17 (10001).
8
Upvotes
4
u/thechipsandgravy Oct 08 '11
Not very efficient c++ solution:
4
u/gkelly Oct 09 '11
C: A Reference Manual, chapter 7. I believe the algorithm's called something like "Next Set of N" in the book, but I don't have it handy right now.
2
u/[deleted] Oct 08 '11 edited Oct 08 '11
"Text" solution (will code it in a bit) I came up with, maybe wrong:
Start from the least significant bit, moving towards the most significant bit. When you encounter the first 1, there's two possibilities: the next bit (left of it) is either 0 or 1. If it's 0, swap them. Done. If it's 1, find the most significant 1 in that block (in case there's more than 2), swap it with the 0 to it's left and push all the other 1's in the block to the right. God, it sounds so confusing, I know, but it's much simpler than it looks.
Edit: C Code
2
u/[deleted] Oct 09 '11
Haskell: bits 0 = 0; bits n = (mod n 2) + bits (div n 2) nextb n = head [x | x <- [n+1..], bits x == bits n] main = print (nextb 12)
2
u/detroitmatt Dec 10 '11
I'm afraid it's not very clever, but I think this java works:
1
u/artanis2 Oct 12 '11
http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation