CODEWITHSUNDEEP
c++bit-manipulationbitwise-operators
pasta64
pasta64

Reputation: 462

Get highest number with n bits

I'd like to get the highest number with n bits in C++. I've written this piece of code but maybe there is a more efficient way.

int A = 22;  // 10110
int max = pow(2, (int) log2(A) + 1) - 1;  // returns 31 (11111)

This code raises 2 to the power of the number of bits of A and subtracts 1.

Edit

Since the question seems unclear here are some more examples to help understand the result I want to achieve.

Upvotes: 0

Views: 1109

Answers (5)

Qix - MONICA WAS MISTREATED
Qix - MONICA WAS MISTREATED

Reputation: 15093

Sounds like a Bit Twiddling problem. This is based on https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2, just without the final increment.

unsigned int v;
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

This works for 32-bit numbers only, though, and is untested.

Upvotes: 2

Michaël Roy
Michaël Roy

Reputation: 6461

The usual way of raises 2 to the power of the number of digits of A and subtracts 1 is much simpler to write and read.

Formula:  (1 << nb_bits) - 1

// example: mask lower 8 bits, same as highest number in 8 bits.

constexpr int mask = (1 << 8) - 1;  // 255

//  <=>    mask = 0b1'0000'0000 - 1  in hex:  0x0100 - 1
//  <=>    mash = 0b0'1111'1111      in hex:  0x00FF

// for numbers made of up to 127 bits, use 128 bits integer: 

// on gcc
__uint128_t largest_in_n_bits(int n) {
    assert(n < 128);
    return (__uint128_t(1) << n) - 1;
}

Upvotes: 1

KamilCuk
KamilCuk

Reputation: 140880

First, implement log2 using How to do an integer log2() in C++? . Then shift to the position one more than the highest bit, and then subtract one to get all bits set.

int A = 22;
unsigned max = (1u << std::bit_width((unsigned)A)) - 1;

Note: this will work up to around UINT_MAX >> 1, as 1u << will overflow.

Upvotes: 4

Marcus M&#252;ller
Marcus M&#252;ller

Reputation: 36327

I've written this piece of code but maybe there is a more efficient way.

I'll assume the question is "can this code be improved"?

Yes, it can.

What your code does is

  1. convert the integer A to a double, implicitly, because log2(double) takes a double argument.
  2. Take the logarithm base 2 of that (double)A using the log2(double) function.
  3. round down that double to the nearest int, then add 1
  4. Convert the result to a double again, then use the pow(double, double) function to approximate 2.0 ** that.
  5. convert the result down, hoping (sadly, incorrectly) that the result is correct.

So, first, the obvious, pow is just useless in your case. Use bit shifts; 1 << k shifts 1 left by k bit positions; the result is 2**k.

Then, detecting the highest set bit in an integer is a solved problem: What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C?

Upvotes: 0

PoneyUHC
PoneyUHC

Reputation: 335

Without any function call, I would propose this algorithm :

int a = 22;
short count = 0;
while(a != 0){
    a >>= 1;
    ++count;
}
for(int i=0; i<count; ++i){
    a |= 1;
    a <<= 1;
}
a >>= 1;
// a is now 31

There may be a classier way to do it, but this one only uses bit shifting.

Upvotes: 0

Related Questions