Find the closest integer with same weight

1 February 2016

Introduction

The count of ones in binary representation of integer number is called the weight of that number. The following algorithm finds the closest integer with the same weight. For example, for 123 (0111 1011)₂, the closest integer number is 125 (0111 1101)₂.

Algorithm

We iterate through bits to find the first pair of consecutive bits that differ. Swapping positions of these two bits will give us the closest integer, either greater than, or lower than our argument.

In order to find exactly the lower or greater closest integer we must compare if the position of the first bit in pair is 0 or 1.

The order we swap bits (in case they differ) will give us:

  • (01)₂ -> (10)₂ - the closest greater integer, because '1' is moving toward MSB positions,
  • (10)₂ -> (01)₂ - the closest lower integer, beacuse '1' is moving toward LSB positions.

Computing functions

The following function will do the work:

func find_closest_integer(N uint64) uint64 {

    var pos uint
    for n := N; n > 0; n >>= 1 {
        if n&1 != n>>1&1 {
            return N ^ ((1 << pos) | (1 << (pos + 1)))
        }
        pos++
    }

    return N
}

Similarly, changing comparison statement to the following,

if n&1 < n>>1&1 {
...
}

gives the closest lower integer, and the other comparison statement,

if n&1 > n>>1&1 {
...
}

gives the closest greater integer.

Efficiency

The above algorithm is of O(n) complexity. Let's make sure of that. Let's show benchmark results when computing `the closest greater` and `the closest lower than integer` for following arguments: 0xFFFE, 0xFFFFFE, and 0xFFFFFFFE. Arguments are choosen on purpose to demonstrate O(n).

go test -bench=.|benchgraph 
? PASS
√ BenchmarkFindGreaterThan_FFFE-4        100000000            15.7 ns/op
√ BenchmarkFindGreaterThan_FFFFFE-4      50000000            27.2 ns/op
√ BenchmarkFindGreaterThan_FFFFFFFE-4    50000000            32.9 ns/op
√ BenchmarkFindLowerThan_FFFE-4          1000000000             2.76 ns/op
√ BenchmarkFindLowerThan_FFFFFE-4        500000000             3.03 ns/op
√ BenchmarkFindLowerThan_FFFFFFFE-4      1000000000             2.79 ns/op
? ok      golang-interview/5-primitive-types/5-4-find-closest-integer-same-weight    12.620s

Waiting for server response ...
=========================================

http://benchgraph.codingberg.com/6

=========================================

And now let's visualize it:

In case of computing `the closest greater integer` we have to iterate through much more bits than in other case - computing `the closest lower than integer`, where we need only single iteration through bits. With increasing number of bits (more iterations (n)), it takes more time to compute, which assure us of O(n) complexity.

Find code samples here github.com/CodingBerg/golang-interview.

By one coder