c++ - 截断二进制数

Question

我想截断整数二进制表示中第一个非零数字之后的每个数字。我还需要它尽可能简单（没有函数或多行代码）。

例如：

// in c++
int int1=7,int2=12,int3=34;   //needs to work for any number

使用某种运算符（可能是按位组合？），我需要这些来给出以下值

int1 -> 4
int2 -> 8
int3 -> 32

截断二进制是我唯一能想到的，所以我对任何想法都持开放态度。

谢谢！

Answer 1

这个函数来自于书Hacker's Delight。

// greatest power of 2 less than or equal to n (floor pow2)

uint32_t flp2(uint32_t n)
{
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n - (n >> 1);
}

我不妨发布相关clp2功能：

// least power of 2 greater than or equal to n (ceiling pow2)

uint32_t clp2(uint32_t n)
{
    n -= 1; 
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}

Answer 2

可以使用一个非常巧妙的技巧：

if ((v & (v - 1)) == 0) {
    return v;
}
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
v >>= 1;
return v;

这个想法是OR在递减值后将所有低于顶部的值“放入”，然后在最后将值递增。我在标准技巧的末尾添加了一个右移，因为原始代码旨在找到2^n大于或等于给定值的最小值。

编辑：我还添加了一个特殊情况2^N，这是同一个列表中的另一个技巧。

这是关于 ideone 的演示。