Perl Weekly Challenge 114: Higher Integer Set Bits

We won't be using a naive algorithm by counting upwards from the given number, getting a binary representation, and comparing the number of bits.

Instead, we will be directly constructing the wanted number.

Let the binary representation of the input number be: \(N = \ldots b_{n+m+2+3}b_{n+m+2}01\underbrace{1 \ldots 1}_{n \geq 0} \underbrace{0 \ldots 0}_{m \geq 0}\).

We are interested in the latter part: a 01 followed by \(n \geq 0\) 1 bits, followed by \(m \geq 0\) 0 bits, and nothing more. (If the binary representation doesn't start with a 0, we can always prepend one.)

We now construct a number \(M\) which starts with the same bits as \(N\) (up to bit \(b_{n+m+2}\)), followed by \(10\), followed by \(m\) 0 bits, followed by \(n\) 1 bits. So, \(M = \ldots b_{n+m+2+3}b_{n+m+2}10\underbrace{0 \ldots 0}_{m \geq 0} \underbrace{1 \ldots 1}_{n \geq 0}\).

Clearly, the number of 1 bits in \(N\) equal the number of 1 bits in \(M\). And there will be no other numbers between \(N\) and \(M\) with the same number of bits. Each of the numbers \(P\) between \(N\) and \(M\) are either of the form: \(P = \ldots b_{n+m+2+3}b_{n+m+2}01\underbrace{1 \ldots 1}_{n \geq 0}b_{m} \ldots b_{1}\), with at least one of last \(m\) bits being a 1, or \(P = \ldots b_{n+m+2+3}b_{n+m+2}10\underbrace{0 \ldots 0}_{m \geq 0}b_{n} \ldots b_{1}\), with at least one of last \(n\) bits being a 0. In the former case, the number as too many 1 bits. In the latter case, the number has not enough 1 bits.