C语言 在 C 中仅使用按位运算符计算 log 的下限？(x)
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/21442088/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Computing the floor of log?(x) using only bitwise operators in C
提问by Brett Cox
For homework, using C, I'm supposed to make a program that finds the log base 2 of a number greater than 0 using only the operators ! ~ & ^ | + << >>. I know that I'm supposed to shift right a number of times, but I don't know how to keep track of the number of times without having any loops or ifs. I've been stuck on this question for days, so any help is appreciated.
对于家庭作业，使用 C，我应该制作一个程序，该程序仅使用运算符来查找大于 0 的数字的对数基数 2 ! ~ & ^ | + << >>。我知道我应该向右移动多次，但我不知道如何在没有任何循环或ifs 的情况下跟踪次数。我已经被这个问题困住了好几天，所以任何帮助表示赞赏。
int ilog2(int x) {
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
}
This is what I have so far. I pass the most significant bit to the end.
这是我到目前为止。我将最重要的部分传递到最后。
采纳答案by Brett Cox
This gets the floor of logbase2 of a number.
这得到了一个数字的 logbase2 的下限。
int ilog2(int x) {
int i, j, k, l, m;
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
// i = 0x55555555
i = 0x55 | (0x55 << 8);
i = i | (i << 16);
// j = 0x33333333
j = 0x33 | (0x33 << 8);
j = j | (j << 16);
// k = 0x0f0f0f0f
k = 0x0f | (0x0f << 8);
k = k | (k << 16);
// l = 0x00ff00ff
l = 0xff | (0xff << 16);
// m = 0x0000ffff
m = 0xff | (0xff << 8);
x = (x & i) + ((x >> 1) & i);
x = (x & j) + ((x >> 2) & j);
x = (x & k) + ((x >> 4) & k);
x = (x & l) + ((x >> 8) & l);
x = (x & m) + ((x >> 16) & m);
x = x + ~0;
return x;
}
回答by Brett Hale
Assumes a 32-bit unsigned int:
假设 32 位unsigned int：
unsigned int ulog2 (unsigned int u)
{
unsigned int s, t;
t = (u > 0xffff) << 4; u >>= t;
s = (u > 0xff ) << 3; u >>= s, t |= s;
s = (u > 0xf ) << 2; u >>= s, t |= s;
s = (u > 0x3 ) << 1; u >>= s, t |= s;
return (t | (u >> 1));
}
Since I assumed >, I thought I'd find a way to get rid of it.
既然我认为>，我想我会找到一种方法来摆脱它。
(u > 0xffff)is equivalent to: ((u >> 16) != 0). If subtract borrows:((u >> 16) - 1)will set the msb, iff (u <= 0xffff). Replace -1with +(~0)(allowed).
(u > 0xffff)相当于：((u >> 16) != 0)。如果减去借用：((u >> 16) - 1)将设置 msb, iff (u <= 0xffff)。替换-1为+(~0)（允许）。
So the condition: (u > 0xffff)is replaced with: (~((u >> 16) + ~0U)) >> 31
所以条件：(u > 0xffff)被替换为：(~((u >> 16) + ~0U)) >> 31
unsigned int ulog2 (unsigned int u)
{
unsigned int r = 0, t;
t = ((~((u >> 16) + ~0U)) >> 27) & 0x10;
r |= t, u >>= t;
t = ((~((u >> 8) + ~0U)) >> 28) & 0x8;
r |= t, u >>= t;
t = ((~((u >> 4) + ~0U)) >> 29) & 0x4;
r |= t, u >>= t;
t = ((~((u >> 2) + ~0U)) >> 30) & 0x2;
r |= t, u >>= t;
return (r | (u >> 1));
}
回答by kuroi neko
Your result is simply the rank of the highest non-null bit.
您的结果只是最高非空位的排名。
int log2_floor (int x)
{
int res = -1;
while (x) { res++ ; x = x >> 1; }
return res;
}
One possible solution is to take this method:
一种可能的解决方案是采用这种方法：
It is based on the additivity of logarithms:
log2(2nx) = log2(x) + n
它基于对数的可加性：
log 2(2 nx) = log 2(x) + n
Let x0be a number of 2nbits (for instance, n=16 for 32 bits).
令x 0为2n位的数目（例如，对于 32 位，n=16）。
if x0> 2n, we can define x1so that
x0= 2nx1and we can say that
E(log2(x0)) = n + E(log2(x1))
We can compute
x1with a binary shift:
x1= x0>> n
如果x 0> 2 n，我们可以定义x 1使得
x 0= 2 nx 1并且我们可以说
E(log 2(x 0)) = n + E(log 2(x 1))
我们可以计算
x 1二进制移位：
x 1= x 0>> n
Otherwise we can simply set X1= X0
否则我们可以简单地设置X 1= X 0
We are now facing the same problem with the remaining upper or lower half of x0
我们现在面临与x 0剩余的上半部分或下半部分相同的问题
By splitting x in half at each step, we can eventually compute E(log2(x)):
通过在每一步将 x 一分为二，我们最终可以计算E(log 2(x))：
int log2_floor (unsigned x)
{
#define MSB_HIGHER_THAN(n) (x &(~((1<<n)-1)))
int res = 0;
if MSB_HIGHER_THAN(16) {res+= 16; $x >>= 16;}
if MSB_HIGHER_THAN( 8) {res+= 8; $x >>= 8;}
if MSB_HIGHER_THAN( 4) {res+= 4; $x >>= 4;}
if MSB_HIGHER_THAN( 2) {res+= 2; $x >>= 2;}
if MSB_HIGHER_THAN( 1) {res+= 1;}
return res;
}
Since your sadistic teacher said you can't use loops, we can hack our way around by computing a value that will be n in case of positive test and 0 otherwise, thus having no effect on addition or shift:
由于您的虐待狂老师说您不能使用循环，我们可以通过计算一个值来解决我们的问题，该值在测试为正的情况下为 n，否则为 0，因此对加法或移位没有影响：
#define N_IF_MSB_HIGHER_THAN_N_OR_ELSE_0(n) (((-(x>>n))>>n)&n)
If the -operator is also forbidden by your psychopatic teacher (which is stupid since processors are able to handle 2's complements just as well as bitwise operations), you can use -x = ~x+1in the above formula
如果-您的精神病老师也禁止运算符（这是愚蠢的，因为处理器能够像按位运算一样处理 2 的补码），您可以-x = ~x+1在上面的公式中使用
#define N_IF_MSB_HIGHER_THAN_N_OR_ELSE_0_WITH_NO_MINUS(n) (((~(x>>n)+1)>>n)&n)
that we will shorten to NIMHTNOE0WNM for readability.
为了便于阅读，我们将缩短为 NIMHTNOE0WNM。
Also we will use |instead of +since we know they will be no carry.
我们也将使用|代替，+因为我们知道它们不会携带。
Here the example is for 32 bits integers, but you could make it work on 64, 128, 256, 512 or 1024 bits integers if you managed to find a language that supports that big an integer value.
这里的示例适用于 32 位整数，但如果您设法找到一种支持大整数值的语言，则可以使其适用于 64、128、256、512 或 1024 位整数。
int log2_floor (unsigned x)
{
#define NIMHTNOE0WNM(n) (((~(x>>n)+1)>>n)&n)
int res, n;
n = NIMHTNOE0WNM(16); res = n; x >>= n;
n = NIMHTNOE0WNM( 8); res |= n; x >>= n;
n = NIMHTNOE0WNM( 4); res |= n; x >>= n;
n = NIMHTNOE0WNM( 2); res |= n; x >>= n;
n = NIMHTNOE0WNM( 1); res |= n;
return res;
}
Ah, but maybe you were forbidden to use #definetoo?
In that case, I cannot do much more for you, except advise you to flog your teacher to death with an old edition of the K&R.
啊，但也许你也被禁止使用#define？在那种情况下，我不能为你做更多，除了建议你用旧版的 K&R 鞭打你的老师。
This leads to useless, obfuscated code that gives off a strong smell of unwashed 70's hackers.
这会导致无用的、混淆的代码散发出强烈的 70 年代黑客的味道。
Most if not all processors implement specific "count leading zeroes" instructions (for instance, clzon ARM, bsron x86 or cntlzon PowerPC) that can do the trick without all this fuss .
大多数（如果不是全部）处理器都实现了特定的“计数前导零”指令（例如，clz在 ARM、bsrx86 或cntlzPowerPC 上），这些指令可以毫不费力地完成任务。
回答by mi al
The question is equal to "find the highest bit of 1 of the binary number"
问题等于“找到二进制数的1的最高位”
STEP 1: set the left of 1 all to 1 like 0x07000000 to 0x07ffffff
第 1 步：将 1 的左边全部设置为 1，例如 0x07000000 到 0x07ffffff
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16); // number of ops = 10
STEP 2: returns count of number of 1's in word and minus 1
第 2 步：返回单词中 1 和负 1 的计数
Reference: Hamming weight
参考：汉明重量
// use bitCount
int m1 = 0x55; // 01010101...
m1 = (m1 << 8) + 0x55;
m1 = (m1 << 8) + 0x55;
m1 = (m1 << 8) + 0x55;
int m2 = 0x33; // 00110011...
m2 = (m2 << 8) + 0x33;
m2 = (m2 << 8) + 0x33;
m2 = (m2 << 8) + 0x33;
int m3 = 0x0f; // 00001111...
m3 = (m3 << 8) + 0x0f;
m3 = (m3 << 8) + 0x0f;
m3 = (m3 << 8) + 0x0f;
x = x + (~((x>>1) & m1) + 1); // x - ((x>>1) & m1)
x = (x & m2) + ((x >> 2) & m2);
x = (x + (x >> 4)) & m3;
// x = (x & m3) + ((x >> 4) & m3);
x += x>>8;
x += x>>16;
int bitCount = x & 0x3f; // max 100,000(2) = 32(10)
// Number of ops: 35 + 10 = 45
return bitCount + ~0;
This is how I do. Thank you~
这就是我的做法。谢谢~
回答by phuclv
If you're allowed to use &then can you use &&? With that you can do conditionals without the need of if
如果您被允许使用，&那么您可以使用&&吗？有了它，你可以在不需要的情况下做条件if
if (cond)
doSomething();
can be done with
可以用
cond && doSomething();
Otherwise if you want to assign value conditionally like value = cond ? a : b;then you may do it with &
否则，如果你想有条件地赋值，value = cond ? a : b;那么你可以这样做&
mask = -(cond != 0); // assuming int is a 2's complement 32-bit type
// or mask = (cond != 0) << 31) >> 31;
value = (mask & a) | (~mask & b);
There are many other ways in the bithacks page:
在bithacks 页面中还有许多其他方式：
int v; // 32-bit integer to find the log base 2 of
int r; // result of log_2(v) goes here
union { unsigned int u[2]; double d; } t; // temp
t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = v;
t.d -= 4503599627370496.0;
r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;
or
或者
unsigned int v; // 32-bit value to find the log2 of
register unsigned int r; // result of log2(v) will go here
register unsigned int shift;
r = (v > 0xFFFF) << 4; v >>= r;
shift = (v > 0xFF ) << 3; v >>= shift; r |= shift;
shift = (v > 0xF ) << 2; v >>= shift; r |= shift;
shift = (v > 0x3 ) << 1; v >>= shift; r |= shift;
r |= (v >> 1);
another way
其它的办法
uint32_t v; // find the log base 2 of 32-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};
v |= v >> 1; // first round down to one less than a power of 2
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];
回答by swsmith
I also was assigned this problem for homework and I spent a significant amount of time thinking about it so I thought I'd share what I came up with. This works with integers on a 32 bit machine. !!x returns if x is zero or one.
我也被分配了这个问题作为家庭作业，我花了大量时间思考它，所以我想我会分享我的想法。这适用于 32 位机器上的整数。!!x 在 x 为零或一时返回。
int ilog2(int x) {
int byte_count = 0;
int y = 0;
//Shift right 8
y = x>>0x8;
byte_count += ((!!y)<<3);
//Shift right 16
y = x>>0x10;
byte_count += ((!!y)<<3);
//Shift right 24 and mask to adjust for arithmetic shift
y = (x>>0x18)&0xff;
byte_count += ((!!y)<<3);
x = (x>>byte_count) & 0xff;
x = x>>1;
byte_count += !!x;
x = x>>1;
byte_count += !!x;
x = x>>1;
byte_count += !!x;
x = x>>1;
byte_count += !!x;
x = x>>1;
byte_count += !!x;
x = x>>1;
byte_count += !!x;
x = x>>1;
byte_count += !!x;
x = x>>1; //8
byte_count += !!x;
return byte_count;
}
