# Perl Weekly Challenge 114: Higher Integer Set Bits

by Abigail

## Challenge

You are given a positive integer $N. Write a script to find the next higher integer having the same number of 1 bits in binary representation as $N.

### Examples

Input: $N = 3 Output: 5  Binary representation of $N is 011. There are two 1 bits. So the next higher integer is 5 having the same the number of 1 bits i.e. 101.

Input: $N = 12 Output: 17  Binary representation of $N is 1100. There are two 1 bits. So the next higher integer is 17 having the same number of 1 bits i.e. 10001.

## Discussion

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.

## Solutions

### Perl

This is just a one liner:

say oct sprintf ("0b0%b" => $_) =~ s {01(1*)(0*)$} {10$2$1}r while <>;


We read the number (<>), get a binary representation, prepend with both a 0 and a 0b (sprintf "0b0%b" => $_), perform the substitution described above (s {01(1*)(0*)$} {10$2$1}r), and turn it into a decimal representation again (oct, which takes a binary number as input if its argument starts with 0b).

Find the full program on GitHub.