截断二进制数

Question

我希望截断整数在二进制表示中第一个非零数字后的所有数字。同时需要尽可能简单（不使用函数或多行代码）。

例如：

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

我需要使用某种运算符（也许是按位组合？）使它们得出以下值：

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

我只能想到二进制截断，所以我愿意听取任何想法。

谢谢！

- Couchy

---

我知道的每种方法都涉及多行代码。你确定你不能在使用它的地方处理函数调用吗？ - Patricia Shanahan

@PatriciaShanahan 我正在进行三重积分，所以不需要。但我想我可以考虑事先存储我需要的值。 - Couchy

Answer 1

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

这里 有详细说明。

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上的演示。

- Sergey Kalinichenko

---

我认为你需要调整一下对于2的幂次方的情况。当我使用输入32运行你的代码时，输出结果为16。或许可以将原始值v保存为old_v，如果v++后的值等于old_v，则不进行最后的移位操作。 - Patricia Shanahan

@PatriciaShanahan 感谢您的留言，我为这个特殊情况添加了一个解决方法。 - Sergey Kalinichenko

谢谢，我对位运算符不是很熟悉，但我假设这检查了所有可能的情况，因此对于大于31的任何内容都需要进行更多的检查（对吗？）。对于我的目的，我需要假设最大数字为2^15，因此我担心这样做会显著减慢过程，而我无法承受（近似积分）。 - Couchy

@user1888743 你不需要执行任何其他检查。假设v是无符号的，这个技巧适用于范围内的所有v值。 - Sergey Kalinichenko

@dasblinkenlight 你会如何在 #define 语句中实现这个，以便你可以将其用作单个值？ - Couchy

@user1888743 为什么不使用可内联的C99函数？宏会非常丑陋... - Sergey Kalinichenko

Answer 2

这个函数来自于书籍《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;
}

- Blastfurnace