Get highest number with n bits

Question

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

Any C++ code that calls `pow()` with two integer values is automatically broken, by default. This is not what `pow()` is for. You might be surprised to learn that, for example, `pow(10,2)` will not produce for you `100`. And, yes, there's a better way, simply by using a constant that the C++ library already defines for you, that means exactly this. — Sam Varshavchik, Jan 16 '23 at 16:24
"Maximize a number" means to set all the bits to the right of the left-most set bit in a number? What is the range of numbers you are want to support? what should happen to negative numbers? — KamilCuk, Jan 16 '23 at 16:26
what does "to maximize a number" mean? Like, mathematically? — Marcus Müller, Jan 16 '23 at 16:26
`pow()` takes the natural logarithm of its first parameter, multiplies it by the 2nd parameter, then raises the mathematical `e` constant to the result. This is calculated using floating point math, and, as you know, [floating point math is broken](https://stackoverflow.com/questions/588004/). As such, you are not guaranteed that `pow(10,2)` will be exactly 100. — Sam Varshavchik, Jan 16 '23 at 16:33
`highest number with n bits` What is "highest number"? Why `0b111111000000....` is not higher than `0b11111`? — KamilCuk, Jan 16 '23 at 16:34
even if you are lucky you'd get `100.0`, but thats not what you want, because its a floating point number while you are workign with integers — 463035818_is_not_an_ai, Jan 16 '23 at 16:35
@pasta64 -- This behavior of floating point not only exists in C++, but in most of the other languages also. The bottom line is to not use floating point functions to solve integer-based problems. — PaulMcKenzie, Jan 16 '23 at 16:36
*"I'd like to get the highest number with n bits"* Please elaborate on that with more examples. Do you want the sequence 1, 3, 7, 15, ...? — Bob__, Jan 16 '23 at 16:39

score 4 · Accepted Answer · answered Jan 16 '23 at 16:36

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.

score 2 · Answer 2 · answered Jan 16 '23 at 17:12

2

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.

answered Jan 16 '23 at 17:12

Qix - MONICA WAS MISTREATED

14,451
16
82
145

For 64-bit numbers, add another `v |= v >> 32;` – user253751 Jan 16 '23 at 17:20
Explanation: all the 1 bits in the original number keep getting copied to the right and eventually fill in every possible spot to the right of where they started. – user253751 Jan 16 '23 at 17:21

Michaël Roy · Answer 3 · 2023-01-16T16:49:31.710

1

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

edited Jan 16 '23 at 16:49

answered Jan 16 '23 at 16:36

Michaël Roy

6,338
1
15
19

2

The problem for the OP is getting `nb_bits`. They need to find that out from the value and that is resulting the expensive log call. – NathanOliver Jan 16 '23 at 16:37
The questoin is literally: **"I'd like to get the highest number with n bits in C++"** – Michaël Roy Jan 16 '23 at 16:51

score 0 · Answer 4 · answered Jan 16 '23 at 16:35

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.

score 0 · Answer 5 · answered Jan 16 '23 at 16:35

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

convert the integer A to a double, implicitly, because log2(double) takes a double argument.
Take the logarithm base 2 of that (double)A using the log2(double) function.
round down that double to the nearest int, then add 1
Convert the result to a double again, then use the pow(double, double) function to approximate 2.0 ** that.
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?

Get highest number with n bits

5 Answers5