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.

• 1000 => 1111
• 1010 => 1111
• 100001 => 111111
• 111 => 111

CodePudding user response：

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.

CodePudding user response：

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;
}

CodePudding user response：

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.

CodePudding user response：

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.

CodePudding user response：

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?