Home | Projects | Notes > Problem Solving > EPI - 5.4. Find a Closest Integer with the Same Weight (bit manipulation)

EPI - 5.4. Find a Closest Integer with the Same Weight (bit manipulation)

Solutions in C

Solution 1

This solution uses bit swapping technique using shift and xor operation.

The key is to finding the algorithm: Swap the two rightmost consecutive bits that differ.

It is assumed that x is not 0, or all 1s.

Complexity Analysis:

• $T=O(n)$$T = O(n)$, where $n$$n$ is the width of the given integer x

• $S=O(1)$$S = O(1)$

Solution:

xxxxxxxxxx
15
1
unsigned long ClosestIntSameBitCount(unsigned long x)
2
{
3
    int i;
4
    
5
    for (i = 0; i < 63; i++)
6
    {
7
        if (((x >> i) & 1) != ((x >> (i + 1)) & 1))
8
        {
9
            x ^= ((1UL << i) | (1UL << (i + 1)));   // swap bits
10
            break;
11
        }
12
    }
13
    
14
    return x;
15
}