那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

如何使用位操作得到大于N且为2的次方的最小的数

RT,比如输入10返回16, 输入24返回32,等等.


注意,是使用位操作且没有循环,也不用表驱动等等.因为这个操作要经常进行,要保证高效,所以不能使用循环(别跟我说用递归,熟悉算法和计算机本质的人都知道递归和循环本质是一样的:);同时,因为不知道需要计算的数据到底有多大,采用表驱动的办法也不可行.

我在网上发帖,最终得到了一个很BT的答案:
int fun(int v)
{
    
float f = (float)(v - 1);  
    
return 1 << ((*(unsigned int*)(&f) >> 23- 126);
}

但是我不知道这个算法的原理是什么,貌似采用了浮点数格式的一些特性,知道的同学请给我一个详尽的解释,在这里先感谢了.

posted on 2008-06-21 15:36 那谁 阅读(4570) 评论(10)  编辑 收藏 引用 所属分类: C\C++算法与数据结构

评论

# re: 如何使用位操作得到大于N且为2的次方的最小的数  回复  更多评论   

很邪恶啊,我还是喜欢简单一些的。。。

int fun(int v)
{
int res = 1;
while (res < v)
res <<= 1;

return res;
}
2008-06-21 16:36 | 大日如来

# re: 如何使用位操作得到大于N且为2的次方的最小的数  回复  更多评论   

其实也不复杂,只要知道float在内存里是怎么存储的就简单的很了
IEEE:
float:
Sign Exponent Mantissa
1bit 8bits 23bits

实际上float的Mantissa是24位,有一个隐含的最高位,且该位一直为‘1’

Mantissa表示1~2之间的数
Expoent=0x7f表示指数0, Expoent>0x7f为正指数,Expoent<0x7f则为负指数
2008-06-21 16:41 | 大日如来

# re: 如何使用位操作得到大于N且为2的次方的最小的数  回复  更多评论   

和BIG-ENDIAN or LITTLE_ENDIAN有关,推荐少用。
2008-06-21 16:51 | 大日如来

# re: 如何使用位操作得到大于N且为2的次方的最小的数  回复  更多评论   

@大日如来
我不觉得和大小端有关系,浮点寄存器和整数寄存器在内存存取上是一致的。
2008-06-22 17:50 | Louix

# re: 如何使用位操作得到大于N且为2的次方的最小的数  回复  更多评论   

刚才做实验验证了一下,这个方法是有Bug的,使用float类型会造成转换时的进位,使用double就可以了,求数字二进表示长度的代码:
double dTarget = ( double )target;
return ( ( *( ( ( unsigned int * ) &dTarget ) + 1 ) ) >> 20 ) - 1023;
这样的代码就和大小端相关了,而且没有其他版效率高。
2008-06-22 18:45 | Louix

# re: 如何使用位操作得到大于N且为2的次方的最小的数  回复  更多评论   

答案是很BT的,我是想不到
2008-06-22 23:00 | 影视剧

# re: 如何使用位操作得到大于N且为2的次方的最小的数  回复  更多评论   

这个算法只是玩一玩了,有助于了解IEEE标准浮点数的构造。
实际应用中整形和浮点的相互转换很花时间,还不如一步步位移来做。
2008-06-25 09:20 | RedNax

# re: 如何使用位操作得到大于N且为2的次方的最小的数  回复  更多评论   

解决问题的关键在于如何找到二进制表示时第一个‘1’出现的位置。‘1’出现在第n位,则将1左移n位即可。
v - 1是不必要的,意图可能是想去掉大日如来所说的“隐含的最高位1”,直接转就可以了,要了反而算出的结果不对,不是float类型转换进位的问题。
f右移23位为的是得到存储在Exponent里的(n-1)+127=n+126,127是常量。再减去126求得n。
利用浮点数存储格式来找到这个n确实是我没想到的,想出这个解法的人思维很发散。
2008-07-21 15:51 | wolfssss

# re: 如何使用位操作得到大于N且为2的次方的最小的数  回复  更多评论   

@wolfssss
float f = (float)(v - 1);
v减不减一的区别在于

float f = (float)(v - 1);
求的是大于等于N且为2的次方的最小的数

float f = (float)(v);
求的是大于N且为2的次方的最小的数
2011-10-16 12:16 | 楚天清秋

# re: 如何使用位操作得到大于N且为2的次方的最小的数  回复  更多评论   

可以下ieee 754 就明白了
2013-02-22 17:07 | mankeyl

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理