CODEWITHSUNDEEP
algorithmbit-manipulation
n00bcoder123
n00bcoder123

Reputation: 119

Smallest number in a range [a,b] with maximum number of '1' in binary representation

Given a range [a,b] (both inclusive) I need to find the smallest number with the maximum number of '1's in binary representation. My current approach is I find the number of bits set in all numbers from a to b and keep track of the maximum. However this is very slow, any faster method?

Upvotes: 2

Views: 560

Answers (2)

user555045
user555045

Reputation: 64903

You can replace the loop in Jarlax' answer by a "parallel suffix OR", like this

uint32_t m = (a ^ b) >> 1;
m |= m >> 1;
m |= m >> 2;
m |= m >> 4;
m |= m >> 8;
m |= m >> 16;
uint32_t res = a | m;
if ((res | b) <= b)
    res = b;
return res;

It generalizes to different sizes integer, using ceil(log(k)) steps in general. The initial test a == b is not necessary, a ^ b would be zero, therefore m is zero, so nothing interesting happens anyway.

Alternatively, here's a completely different approach: keep changing the lowest 0 to a 1 until it is no longer possible.

unsigned x = a;
while (x < b) {
    unsigned newx = (x + 1) | x; // set lowest 0
    if (newx <= b)
        x = newx;
    else
        break;
}
return x;

Upvotes: 2

Jarlax
Jarlax

Reputation: 1576

Let's find most significant bit which is different in a and b. It will be 0 in a, 1 in b. If we place all other bits to the right to 1 - resulting number will be still in range [a; b]. And it will the single number with maximum number of ones in representation.

EDIT. The result of this algorithm always returns the number with n-1 bits set to one, where n is number of bits which can be changed. As pointed in comments - there is a bug in case if all of there n bits in b are set to 1. Here is the fixed code snippet:

int maximizeBits(int a, int b) {
    if (a == b) {
        return a;
    }
    int m = a ^ b, pow2 = 1; // MSB of m=a^b is bit that we need to find
    while (m > pow2) { // Set other bits to 0
        if ((m & pow2) != 0) {
            m ^= pow2;
        }
        pow2 <<= 1;
    }

    int res = a | (m - 1); // Now m is in form of 2^n and m - 1 would be mask of n-1 bits
    if ((res | b) <= b) { // Fix of problem if all n bits in b are set to 1
        res = b;
    }
    return res;
}

Upvotes: 2

Related Questions