c++ 获取n位的最大数

bihw5rsg  于 2023-01-18  发布在  其他
关注(0)|答案(5)|浏览(178)

我想在C++中得到n位的最大数,我写了这段代码,但也许有一个更有效的方法。

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

此代码将2自乘到A的位数的幂并减去1。

    • 编辑**

由于这个问题似乎不清楚,这里有一些更多的例子来帮助理解我想要达到的结果。

  • 1000 =〉1111
  • 1010 =〉1111
  • 100001 =〉111111
  • 111 =〉111
yvgpqqbh

yvgpqqbh1#

首先,使用How to do an integer log2() in C++?实现log2,然后移位到比最高位多一位的位置,再减一位以设置所有位。

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

注意:这将工作到大约UINT_MAX >> 1,因为1u <<将溢出。

omvjsjqw

omvjsjqw2#

这听起来像是一个小问题,它基于https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2,只是没有最后的增量。

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

不过,这只适用于32位数字,而且未经测试。

kgsdhlau

kgsdhlau3#

将2自乘到A的位数的幂再减1的通常方法写和读要简单得多。

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

ldfqzlk84#

在没有任何函数调用的情况下,我建议使用以下算法:

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

也许有一种更好的方法来做这件事,但这一个只使用位移位。

lawou6xi

lawou6xi5#

我已经写了这段代码,但也许有一个更有效的方法。
我假设问题是“这段代码可以改进吗”?
是的,它可以。
你的代码做的是
1.隐式地将整数A转换为double,因为log2(double)接受double参数。
1.使用log2(double)函数对该(double)A取以2为底的对数。
1.将double向下舍入到最接近int,然后加1
1.再次将结果转换为double,然后使用pow(double, double)函数近似2.0**。
1.向下转换结果,希望(遗憾的是,错误地)结果是正确的。
因此,首先,显而易见的是,pow在您的情况下毫无用处。1 << k将1左移k个位位置;结果是2**k。
那么,检测整数中的最高设置位是一个已解决的问题:What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C?

相关问题