文档章节

位运算的运用

kongjun
 kongjun
发布于 2015/06/04 15:09
字数 707
阅读 14
收藏 0

(1) 判断int型变量a是奇数还是偶数
a&1 = 0 偶数
a&1 = 1 奇数
(2) 取int型变量a的第k位 (k=0,1,2……sizeof(int)),即a>>k&1
(3) 将int型变量a的第k位清0,即a=a&~(1 < <k)
(4) 将int型变量a的第k位置1, 即a=a|(1 <<k)
(5) int型变量循环左移k次,即a=a < >16-k (设sizeof(int)=16)
(6) int型变量a循环右移k次,即a=a>>k|a < <16-k (设sizeof(int)=16)
(7)整数的平均值
对于两个整数x,y,如果用 (x+y)/2 求平均值,会产生溢出,因为 x+y 可能会大于INT_MAX,但是我们知道它们的平均值是肯定不会溢出的,我们用如下算法:
int average(int x, int y) //返回X,Y 的平均值
{
return (x&y)+((x^y)>>1);
}
(8)判断一个整数是不是2的幂,对于一个数 x >= 0,判断他是不是2的幂
boolean power2(int x)
{
return ((x&(x-1))==0)&&(x!=0);
}
(9)不用temp交换两个整数
void swap(int x , int y)
{
x ^= y;
y ^= x;
x ^= y;
}
(10)计算绝对值
int abs( int x )
{
int y ;
y = x >> 31 ;
return (x^y)-y ; //or: (x+y)^y
}
(11)取模运算转化成位运算 (在不产生溢出的情况下)
a % (2^n) 等价于 a & (2^n – 1)
(12)乘法运算转化成位运算 (在不产生溢出的情况下)
a * (2^n) 等价于 a < < n
(13)除法运算转化成位运算 (在不产生溢出的情况下)
a / (2^n) 等价于 a>> n
例: 12/8 == 12>>3
(14) a % 2 等价于 a & 1
(15) if (x == a) x= b;
else x= a;
等价于 x= a ^ b ^ x;
(16) x 的 相反数 表示为 (~x+1)

实例

功能 | 示例 | 位运算
———————-+—————————+——————–
去掉最后一位 | (101101->10110) | x >> 1
在最后加一个0 | (101101->1011010) | x < < 1
在最后加一个1 | (101101->1011011) | x < < 1+1
把最后一位变成1 | (101100->101101) | x | 1
把最后一位变成0 | (101101->101100) | x | 1-1
最后一位取反 | (101101->101100) | x ^ 1
把右数第k位变成1 | (101001->101101,k=3) | x | (1 < < (k-1))
把右数第k位变成0 | (101101->101001,k=3) | x & ~ (1 < < (k-1))
右数第k位取反 | (101001->101101,k=3) | x ^ (1 < < (k-1))
取末三位 | (1101101->101) | x & 7
取末k位 | (1101101->1101,k=5) | x & ((1 < < k)-1)

取右数第k位 | (1101101->1,k=4) | x >> (k-1) & 1

把末k位变成1 | (101001->101111,k=4) | x | (1 < < k-1)
末k位取反 | (101001->100110,k=4) | x ^ (1 < < k-1)
把右边连续的1变成0 | (100101111->100100000) | x & (x+1)
把右起第一个0变成1 | (100101111->100111111) | x | (x+1)
把右边连续的0变成1 | (11011000->11011111) | x | (x-1)
取右边连续的1 | (100101111->1111) | (x ^ (x+1)) >> 1
去掉右起第一个1的左边 | (100101000->1000) | x & (x ^ (x-1))
判断奇数 (x&1)==1
判断偶数 (x&1)==0

© 著作权归作者所有

共有 人打赏支持
kongjun
粉丝 7
博文 98
码字总数 40811
作品 0
杭州
程序员
私信 提问
二进制中1的个数

这是一个经典的面试题,我们想知道一个二进制中1的个数,首先我们应该判断整数二进制表中最右边的一位是不是1,接着把输入的整数右移一位,此时原来处于右边倒数第二为被移到最右边了,再判断...

柠檬dream
2017/11/26
0
0
优秀程序员不得不知道的20个位运算技巧

一 提起位运算,人们往往想到它的高效性,无论是嵌入式编程还是优化系统的核心代码,适当的运用位运算总是一种迷人的手段,或者当您求职的时候,在代码中写入 适当的位运算也会让您的程序增加...

lizuochao
2012/12/12
0
0
JAVA中不提供有符号类型,只是为了平台移植性?

有符号无符号的差别,可以就在于某些数表示范围的大小; 对于编程来讲,可能就存在这种应用场景(无符号数的运算、运用); 并且,从底层机器码实现来说,无符号数运算有可能要精简于有符号数...

380121850Lee
2017/05/14
120
2
java二进制相关基础

转载请注明原创出处,谢谢! 说在前面 之前在JVM菜鸟进阶高手之路十(基础知识开场白)的时候简单提到了二进制相关问题,最近在看RocketMQ的源码的时候,发现涉及二进制的内容蛮多,jdk源码里...

匠心零度
2017/12/05
0
0
算法学习笔记(5)-------位运算的tips

在计算机中所有数据都是以二进制的形式储存的。位运算其实就是直接对在内存中的二进制数据进行操作,因此处理数据的速度非常快。 在实际编程中,如果能巧妙运用位操作,完全可以达到四两拨千...

亭芳
2014/03/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Ugly Number(leetcode263)

Write a program to check whether a given number is an ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. Example 1: Input: 6Output: true......

woshixin
25分钟前
1
0
深度模型从研者 眼里的 似然估计 & Hessain 海森矩阵 & Fisher Information (费雪信息)

深度模型的训练的基本依据是最小化模型拟合数据的误差。旨在不仅知其然(如何构建和训练一个深度模型),还应知其所以然(为什么这样训练,可以做哪些优化)。我们就会发现,有很多研究者,在...

刘小米_思聪
29分钟前
0
0
阿里巴巴智能监控新场景的探索

摘要: 智能监控是智能运维的子领域,详细分析。 作者简介 王肇刚 阿里巴巴全球运行指挥中心高级技术专家 智能监控是智能运维的子领域,我们说的监控,探讨的更多是在监控策略,因为可能从数...

阿里云官方博客
31分钟前
1
0
【双十二】12 月 12 日 12 点 12 分限量抢福利,云计算不剁手!

活动详情 1.首充豪礼 双十二当日,新用户首充 200 元送 200 元代金券!仅限前 88 名!先到先得!拼手速!(新用户指 12 月 12 日前已完成注册但从未充值过的用户)
 2.超值返券 双十二当日,...

七牛云
57分钟前
3
0
Calculate Linux 发布 18 LXQt是基于Gentoo的发行版

导读 Calculate Linux 是一个基于 Gentoo 并与 Gentoo 完全兼容的滚动更新发行版家族,专为企业环境下的快速部署而优化。其提供多个不同的分支版本,分别适用于桌面、服务器等应用场景。该项...

问题终结者
59分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部