# Perl Weekly Challenge 114: Higher Integer Set Bits

by Abigail

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.