在没有循环的情况下从 C++ 中的 int 中提取 n 个最高有效非零位
-
16-12-2019 - |
题
我想从 C++ 中的整数中提取 n 个最高有效位,并将这 n 位转换为整数。
例如
int a=1200;
// its binary representation within 32 bit word-size is
// 00000000000000000000010010110000
现在我想从该表示中提取 4 个最高有效数字,即1111
00000000000000000000010010110000
^^^^
并将它们再次转换为整数(十进制 1001 = 9)。
一个没有循环的简单 C++ 函数怎么可能?
解决方案
某些处理器有一条指令来计算整数的前导二进制零,而某些编译器则具有允许您使用该指令的内联函数。例如,使用 GCC:
uint32_t significant_bits(uint32_t value, unsigned bits) {
unsigned leading_zeros = __builtin_clz(value);
unsigned highest_bit = 32 - leading_zeros;
unsigned lowest_bit = highest_bit - bits;
return value >> lowest_bit;
}
为了简单起见,我省略了对请求的位数是否可用的检查。对于微软的编译器来说,内在函数被称为 __lzcnt
.
如果您的编译器没有提供该内在函数,并且您的处理器没有合适的指令,那么快速计算零的一种方法是使用二分搜索:
unsigned leading_zeros(int32_t value) {
unsigned count = 0;
if ((value & 0xffff0000u) == 0) {
count += 16;
value <<= 16;
}
if ((value & 0xff000000u) == 0) {
count += 8;
value <<= 8;
}
if ((value & 0xf0000000u) == 0) {
count += 4;
value <<= 4;
}
if ((value & 0xc0000000u) == 0) {
count += 2;
value <<= 2;
}
if ((value & 0x80000000u) == 0) {
count += 1;
}
return count;
}
其他提示
速度并不快,但是 (int)(log(x)/log(2) + .5) + 1
会告诉您最高有效非零位的位置。从那里完成算法相当简单。
这个似乎工作(用uint32完成了c#然后移植到bjarne道歉):
unsigned int input = 1200;
unsigned int most_significant_bits_to_get = 4;
// shift + or the msb over all the lower bits
unsigned int m1 = input | input >> 8 | input >> 16 | input >> 24;
unsigned int m2 = m1 | m1 >> 2 | m1 >> 4 | m1 >> 6;
unsigned int m3 = m2 | m2 >> 1;
unsigned int nbitsmask = m3 ^ m3 >> most_significant_bits_to_get;
unsigned int v = nbitsmask;
unsigned int c = 32; // c will be the number of zero bits on the right
v &= -((int)v);
if (v>0) c--;
if ((v & 0x0000FFFF) >0) c -= 16;
if ((v & 0x00FF00FF) >0) c -= 8;
if ((v & 0x0F0F0F0F) >0 ) c -= 4;
if ((v & 0x33333333) >0) c -= 2;
if ((v & 0x55555555) >0) c -= 1;
unsigned int result = (input & nbitsmask) >> c;
.
我假设你只使用整数数学。
我使用了来自@ OlicharlesWorth的链接的一些代码,你可以通过使用那里的尾随零零的LUT来删除条件。
不隶属于 StackOverflow