g**e
发帖数: 6127 | 1 求32bit int log base 2. 越快越好 |
d**********x
发帖数: 4083 | 2 就是msb位置啊
用类似2分的办法可以做到log(bits)的速度
其实我记得cpu貌似直接有指令可以取
【在 g**e 的大作中提到】
: 求32bit int log base 2. 越快越好
|
g**e
发帖数: 6127 | 3 yes, clz 这题考刚毕业的还可以，考工作七八年的是不是太偏了点
【在 d**********x 的大作中提到】
: 就是msb位置啊
: 用类似2分的办法可以做到log(bits)的速度
: 其实我记得cpu貌似直接有指令可以取
|
A**u
发帖数: 2458 | 4 把int表示成2的倍数
比如
3 = 1+2 => 0 + 1 = 1
10 = 2+ 8 => 1 + 3 = 4
15 = 8+4+2+1 => 3 + 2 + 1 + 0 = 7
所以和count 1算法类似，做些小修改
【在 g**e 的大作中提到】
: 求32bit int log base 2. 越快越好
|
l*****a
发帖数: 14598 | 5 不是查对数表吗?O(1)
【在 g**e 的大作中提到】
: 求32bit int log base 2. 越快越好
|
d**e
发帖数: 6098 | 6 我不会。。。
【在 g**e 的大作中提到】
: yes, clz 这题考刚毕业的还可以，考工作七八年的是不是太偏了点
|
g**e
发帖数: 6127 | 7 我会这个 Math.log(n)/Math.log(2)，在我的机器上比clz慢10倍
【在 d**e 的大作中提到】
: 我不会。。。
|
M********5
发帖数: 715 | |
b******7
发帖数: 92 | 9 算法思想：求n二进制中最高位的1所在的位置（32种可能），brute force或二分
int log(int n)
{
int t = -1;
while(n > 0)
{
n=n>>1;
t++;
}
return t;
}
int log(int n)
{
int t = -1;
int low = 0, high = sizeof(int)*8-1;//31
while(low <= high)
{
int mid = low + (high - low)/2;
int mask = 1 << mid;
if(mask & n)
{
t = mid;
}
if(mask >= n)
high = mid -1;
else
low = mid + 1;
}
return t;
}
【在 g**e 的大作中提到】
: 求32bit int log base 2. 越快越好
|
k***x
发帖数: 6799 | 10 他是研究（面试）别人吧，跟被人研究（面试）区别大了去了。。。
【在 M********5 的大作中提到】
: 门神你真的也开始准备面试题啦～～～
|
e***s
发帖数: 799 | 11 我感觉二分好像不会比BF快，因为 每次都1 << mid。说不定更耗时
【在 b******7 的大作中提到】
: 算法思想：求n二进制中最高位的1所在的位置（32种可能），brute force或二分
: int log(int n)
: {
: int t = -1;
: while(n > 0)
: {
: n=n>>1;
: t++;
: }
: return t;
|
l*********8
发帖数: 4642 | 12 答案要求是double数据吧？
【在 g**e 的大作中提到】
: 求32bit int log base 2. 越快越好
|
a*****s
发帖数: 1121 | 13 哥们，您这方法不对，7×7=49了。
不能用加法分开在做log和的。您得先了解一下对数运算法则。log16=log（4×4）=
log4+log4
【在 A**u 的大作中提到】
: 把int表示成2的倍数
: 比如
: 3 = 1+2 => 0 + 1 = 1
: 10 = 2+ 8 => 1 + 3 = 4
: 15 = 8+4+2+1 => 3 + 2 + 1 + 0 = 7
: 所以和count 1算法类似，做些小修改
|
