位运算技巧位运算技巧
此文打算讲一些不常见的位运算用法
问题:你要计算n+1，你怎么写,
答:n+1就是n+1啊，除了n+1还有怎么写,
解答:-~n
问题:如果要n-1呢,
解答:~-n
问题:要去掉一个二进制数最低位上第一个出现的1，比如6->4, 14->12, 5->4，怎么办, 解答:n & (n-1) 或者 n - (n & -n)
问题，要得到一个二进制数最低位上第一个出现的1，比如6->2, 7->1, 12->4，怎么办, 解答:同理可得:n - (n & (n-1)) 或者 n & -n ...
位运算技巧
此文打算讲一些不常见的位运算用法
问题:你要计算n+1，你怎么写,
答:n+1就是n+1啊，除了n+1还有怎么写,
解答:-~n
问题:如果要n-1呢,
解答:~-n
问题:要去掉一个二进制数最低位上第一个出现的1，比如6->4, 14->12, 5->4，怎么办, 解答:n & (n-1) 或者 n - (n & -n)
问题，要得到一个二进制数最低位上第一个出现的1，比如6->2, 7->1, 12->4，怎么办, 解答:同理可得:n - (n & (n-1)) 或者 n & -n
问题:判断一个数是不是2的幂
解答:(n&(n-1))==0 && n>0 或者 n>0 && (n & -n)>0
问题:编写sign函数，参数为int n，返回值当n为负数返回-1，正数返回1，0返回0 解答1:return !!n - (((unsigned)n>>31)<<1) 解答2:return ( (x>>31) | ((unsigned)-x>>31) )
问题:求两个正整数的平均值，要考虑溢出的问题
解答:这个计算办法可以保证不会受到溢出问题的影响:(x&y)+((x^y)>>1)
问题:求一个比n大的，并且是最小的2的幂，比如3->4, 6->8, 100->128, 256->512
解答:
int calc(int n)
{
n |= n>>1;
n |= n>>2;
n |= n>>4;
n |= n>>8;
n |= n>>16;
return n+1;
}
问题:求一个int的，以2为底的对数的值的整数部分，比如4的对数是2，10的对数是3，你会怎么写代码呢,
有的人说，用对数换底公式:(int)(log(n)/log(2)) 问题是这样的话，计算速度会非常的慢。
又有人说，我用右移位解决，看移位多少次后，n变成1
这个办法比前一种快很多，但是，最坏情况下也要循环31次才得到结果
还有人说，结果只会是0-31，我把1,2,4,8,16,...全部先保存到数组里，然后二分出那个数在哪个区间，
就知道要移位多少次了。这种比前一种更快，但最坏也要5次二分才得到结果，有没有比这种更快的办法呢,
答:
#include
unsigned log2(unsigned n)
{
double d = (double)n;
unsigned long long * p = (unsigned long long*)&d;
unsigned long long r = *p;
return (unsigned)((r>>52)-0x3FF); }
int main()
{
unsigned n;
while (scanf("%u", &n)!=EOF)
{
printf("%u\n", log2(n));
}
return 0;
}
如果要用VC6编译的话，请把long long替换为__int64
输入的数只要在int范围内，转化成double不会产生任何的传入误差(float会发生) 此代码计算速度非常的快～
int
log2(unsigned a)
{
int y;
double x = frexp(static_cast(a), &y);
return y - 1;
}
本文档为【位运算技巧】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483