先交代下位运算的基础知识
a & b
a | b
a ^ b
~a
a << b
a >> b
位运算应用口诀
清零取反要用与，某位置一可用或，
若要用反和交换，轻轻松松用异或。
移位运算
要点 1 它们都是双目运算符，两个运算分量都是整形，结果也是整形。
2 "<<" 左移：右边空出的位上补0，左边的位将从字头挤掉，其值相当于乘2。
3 ">>"右移：右边的位被挤掉。对于左边移出的空位，如果是正数则空位补0，若为负数，可能补0或补1，这取决于所用的计算机系统和整数有无符号，可以查看http://dsqiu.iteye.com/blog/1687944 可以找到说明。
4 ">>>"运算符，右边的位被挤掉，对于左边移出的空位一概补上0。
二进制补码运算公式：
-x = ~x + 1 = ~(x-1)
~x = -x-1
-(~x) = x+1
~(-x) = x-1
x+y = x - ~y - 1 = (x|y)+(x&y)
x-y = x + ~y + 1 = (x|~y)-(~x&y)
x^y = (x|y)-(x&y)
x|y = (x&~y)+y
x&y = (~x|y)-~x
x==y: ~(x-y|y-x)
x!=y: x-y|y-x
x< y: (x-y)^((x^y)&((x-y)^x))
x<=y: (x|~y)&((x^y)|~(y-x))
x< y: (~x&y)|((~x|y)&(x-y))//无符号x,y比较
x<=y: (~x|y)&((x^y)|~(y-x))//无符号x,y比较
应用举例
(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<<k|a>>sizeof(int)-k
(6) int型变量a循环右移k次，即a=a>>k|a<<sizeof(int)-k
(7)整数的平均值
对于两个整数x,y，如果用 (x+y)/2 求平均值，会产生溢出，因为 x+y 可能会大于INT_MAX，但是我们知道它们的平均值是肯定不会溢出的，我们用如下算法：
int average(int x, int y) //返回X,Y 的平均值
{
return (x&y)+((x^y)>>1);
}
x+y= x&y>>1+x^y;
(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;
}
y=y^y^x;y^y=0;0^x=x;
(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; //这里是有问题的：x=a^b^x;只有当x=b时才有x=a;
(16) x 的 相反数 表示为 (~x+1)
╔
(17)把最后一位变成1 | (101100->101101) | x | 1
(18)把最后一位变成0 | (101101->101100) | x | 1-1
(19)最后一位取反 | (101101->101100) | x ^ 1
(20)右数第k位取反 | (101001->101101,k=3) | x ^ (1 << (k-1))
(21)取末k位 | (1101101->1101,k=5) | x & (1 << k-1)
(22)取右数第k位 | (1101101->1,k=4) | x >> (k-1) & 1
(23)把末k位变成1 | (101001->101111,k=4) | x | (1 << k-1)
(24)末k位取反 | (101001->100110,k=4) | x ^ (1 << k-1)
(25)把右边连续的1变成0 | (100101111->100100000) | x & (x+1)
(26)把右起第一个0变成1 | (100101111->100111111) | x | (x+1)
(27)把右边连续的0变成1 | (11011000->11011111) | x | (x-1)
(28)取右边连续的1 | (100101111->1111) | (x ^ (x+1)) >> 1
(29)去掉右起第一个1的左边 | (100101000->1000) | x & (x ^ (x-1))
对连续的处理，就是要知道连续的位数，再做操作即可。
╝②
╔
符号函数：sign(x) = -1, x<0; 0, x == 0 ; 1, x > 0
int sign(int x)
{
return (x>>31) | (unsigned(-x))>>31 ;//x=-2^31时失败(^为幂)
}
三值比较：cmp(x,y) = -1, x<y; 0, x==y; 1, x > y
int cmp( int x, int y )
{
return (x>y)-(x-y) ;
}
doz=x-y, x>=y; 0, x<y
int doz(int x, int y )
{
int d ;
d = x-y ;
return d & ((~(d^((x^y)&(d^x))))>>31) ;
}
int max(int x, int y )
{
int m ;
m = (x-y)>>31 ;
return y & m | x & ~m ;
}
不使用第三方交换x,y:
1.x ^= y ; y ^= x ; x ^= y ;
2.x = x+y ; y = x-y ; x = x-y ;
3.x = x-y ; y = y+x ; x = y-x ;
4.x = y-x ; x = y-x ; x = x+y ;
下舍入到2的k次方的倍数:
1.x & ((-1)<<k)
2.(((unsigned)x)>>k)<<k
上舍入：
1. t = (1<<k)-1 ; x = (x+t)&~t ;
2.t = (-1)<<k ; x = (x-t-1)&t ;
位计数,统计1位的数量：
1.
int pop(unsigned x)
{
x = x-((x>>1)&0x55555555) ;
x = (x&0x33333333) + ((x>>2) & 0x33333333 ) ;
x = (x+(x>>4)) & 0x0f0f0f0f ;
x = x + (x>>8) ;
x = x + (x>>16) ;
return x & 0x0000003f ;
}
2.
int pop(unsigned x) {
static char table[256] = { 0,1,1,2, 1,2,2,3, ...., 6,7,7,8 } ;
return table[x&0xff]+table[(x>>8)&0xff]+table[(x>>16)&0xff]+table[(x>>24)] ;
}
奇偶性计算:
x = x ^ ( x>>1 ) ;
x = x ^ ( x>>2 ) ;
x = x ^ ( x>>4 ) ;
x = x ^ ( x>>8 ) ;
x = x ^ ( x>>16 ) ;
结果中位于x最低位，对无符号x,结果的第i位是原数第i位到最左侧位的奇偶性
位反转：
unsigned rev(unsigned x)
{
x = (x & 0x55555555) << 1 | (x>>1) & 0x55555555 ;
x = (x & 0x33333333) << 2 | (x>>2) & 0x33333333 ;
x = (x & 0x0f0f0f0f) << 4 | (x>>4) & 0x0f0f0f0f ;
x = (x<<24) | ((x&0xff00)<<8) | ((x>>8) & 0xff00) | (x>>24) ;
return x ;
}
递增位反转后的数：
unsigned inc_r(unsigned x)
{
unsigned m = 0x80000000 ;
x ^= m ;
if( (int)x >= 0 )
do { m >>= 1 ; x ^= m ; } while( x < m ) ;
return x ;
}
混选位：
abcd efgh ijkl mnop ABCD EFGH IJKL MNOP->aAbB cCdD eEfF gGhH iIjJ kKlL mMnN oOpP
unsigned ps(unsigned x)
{
unsigned t ;
t = (x ^ (x>>8)) & 0x0000ff00; x = x ^ t ^ (t<<8) ;
t = (x ^ (x>>4)) & 0x00f000f0; x = x ^ t ^ (t<<4) ;
t = (x ^ (x>>2)) & 0x0c0c0c0c; x = x ^ t ^ (t<<2) ;
t = (x ^ (x>>1)) & 0x22222222; x = x ^ t ^ (t<<1) ;
return x ;
}
位压缩：
选择并右移字x中对应于掩码m的1位的位,如：compress(abcdefgh,01010101)=0000bdfh
compress_left(x,m)操作与此类似，但结果位在左边: bdfh0000.
unsigned compress(unsigned x, unsigned m)
{
unsigned mk, mp, mv, t ;
int i ;
x &= m ;
mk = ~m << 1 ;
for( i = 0 ; i < 5 ; ++i ) {
mp = mk ^ ( mk << 1) ;
mp ^= ( mp << 2 ) ;
mp ^= ( mp << 4 ) ;
mp ^= ( mp << 8 ) ;
mp ^= ( mp << 16 ) ;
mv = mp & m ;
m = m ^ mv | (mv >> (1<<i) ) ;
t = x & mv ;
x = x ^ t | ( t >> ( 1<<i) ) ;
mk = mk & ~mp ;
}
return x ;
}
位置换：
用32个5位数表示从最低位开始的位的目标位置，结果是一个32*5的位矩阵，
将该矩阵沿次对角线转置后用5个32位字p[5]存放。
SAG(x,m) = compress_left(x,m) | compress(x,~m) ;
准备工作：
void init( unsigned *p ) {
p[1] = SAG( p[1], p[0] ) ;
p[2] = SAG( SAG( p[2], p[0]), p[1] ) ;
p[3] = SAG( SAG( SAG( p[3], p[0] ), p[1]), p[2] ) ;
p[4] = SAG( SAG( SAG( SAG( p[4], p[0] ), p[1]) ,p[2]), p[3] ) ;
}
实际置换：
int rep( unsigned x ) {
x = SAG(x,p[0]);
x = SAG(x,p[1]);
x = SAG(x,p[2]);
x = SAG(x,p[3]);
x = SAG(x,p[4]);
return x ;
}
二进制码到GRAY码的转换:
unsigned B2G(unsigned B )
{
return B ^ (B>>1) ;
}
GRAY码到二进制码:
unsigned G2B(unsigned G)
{
unsigned B ;
B = G ^ (G>>1) ;
B = G ^ (G>>2) ;
B = G ^ (G>>4) ;
B = G ^ (G>>8) ;
B = G ^ (G>>16) ;
return B ;
}
找出最左0字节的位置:
int zbytel( unsigned x )
{
static cahr table[16] = { 4,3,2,2, 1,1,1,1, 0,0,0,0, 0,0,0,0 } ;
unsigned y ;
y = (x&0x7f7f7f7f) + 0x7f7f7f7f ;
y = ~(y|x|0x7f7f7f7f) ;
return table[y*0x00204081 >> 28] ;//乘法可用移位和加完成
}
交换C++对象
template <typename T>
void swap(T& obj1, T& obj2)
{
const int sizeOfObj = sizeof(T);
char* pt1 = (char*)&obj1;
char* pt2 = (char*)&obj2;
for (size_t i=0; i<sizeOfObj; i++)
{
pt1[i] ^= pt2[i];
pt2[i] ^= pt1[i];
pt1[i] ^= pt2[i];
}
}
查看对象在内存中的位值
string bitsOfUChar(unsigned char c)
{
const int numOfBitsInUChar = 8;
unsigned int mask = (1<<7);
string result(8, '0');
for (size_t i=0; i<numOfBitsInUChar; i++)
{
if ( mask & c)
result[i] = '1';
mask >>= 1;
}
return result;
}
template <typename T>
string bitsInMemory(const T& obj)
{
int sizeOfObj = sizeof(obj);
unsigned char* pt = (unsigned char*)&obj;
string result;
for (size_t i=0; i<sizeOfObj; i++)
{
result += bitsOfUChar(pt[i]);
result += ' ';
}
return result;
}
比如bitsInMemory(12)，会输出00001100 00000000 00000000 00000000, 我就知道我自己的机器是小尾顺序的了。
╝③
╔
题目：1.二进制1的个数，2.前导0的个数，3.二进制逆序，4.二进制循环移位，5.高低位交换，6.当然还有很多变形题
二进制1的个数
计算二进制1的个数，位运算可以有多种方法，本文实现了三种方法，前两种思想基本一样，细节不同，可对比看一下，欢迎讨论，代码如下
#include<stdio.h>
int bitcount_1(unsigned x); // 移位 n 次
int bitcount_2(unsigned x); // 移位 <= n 次
int bitcount_3(unsigned x); // 移位 count 次
void displaybits(int x); // 打印二进制
void main()
{
int y = 521;
displaybits(y);
printf("%d\n",bitcount_3(y));
}
int bitcount_1(unsigned x)
{
int count = 0;
for(unsigned i = 1 << 31; i > 0; i >>= 1)//屏蔽码一般使用unsigned
{
if(x & i)
{
++count;
}
}
return count;
}
int bitcount_2(unsigned x)
{
int count = 0;
for(; x > 0; x >>= 1)
{
if(x & 1)
{
++count;
}
}
return count;
}
int bitcount_3(unsigned x)
{
int count = 0;
for(; x != 0; x &= (x-1))
{
++count;
}
return count;
}
void displaybits(int x)
{
for(unsigned i = (1 << 31); i > 0; i >>= 1) //屏蔽码一般使用unsigned
{
printf("%c",x & i ? '1' : '0');
}
printf("\n");
}
前导0的个数
我的做法就是简单的使用屏蔽码自左向右做一个遍历计数，可参照上题打印二进制验证，这里不罗列测试程序。
int prezeroCount(int x)
{
int count = 0;
unsigned mask = 1 << 31; //屏蔽码一般使用unsigned
while(0 == (x & mask))
{
++count;
x <<= 1;
}
return count;
}
二进制逆序
我的想法是从右到左取位存在字符数组中，然后打印即可#include<stdio.h>
#define INTBIT 32
void bitreverse(char *s, int x);
void main()
{
int x = 1314520; //逆序为00011011011100000010100000000000
char s[INTBIT+1] = {0};
bitreverse(s,x);
printf("%s\n",s);
}
void bitreverse(char *s, int x)
{
int i = 0;
for(; i < INTBIT; x >>= 1)
{
s[i++] = x & 1 ? '1' : '0';
}
s[i] = '\0';
}
二进制循环移位
编写一个函数shift(x,n)，该函数返回将x循环右移（即从最右端移出的位将从最左端移入）n（二进制）位后所得到的值。
该题的解决思路其实就类似于《编程之美》中“数组循环移位”的思想，这里不再罗列分析。
根据位运算的不同变换，我提供了两种实现，其中第二种实现比较直观简单，欢迎讨论。
#include<stdio.h>
#define INTSEPR 32
void displaybits(int x);
void shift_1(int &x, int n);
void shift_2(int &x, int n);
void main()
{
int x = 52, y = 52;
displaybits(x);
shift_1(x,13);
displaybits(x);
shift_2(y,13);
displaybits(y);
}
void displaybits(int x)
{
for(unsigned i = (1 << 31); i > 0; i >>= 1)
{
printf("%c",x & i ? '1' : '0');
}
printf("\n");
}
void shift_1(int &x, int n)
{
n %= INTSEPR;
unsigned i = (x & ~(~0<<n)) << (INTSEPR-n);
unsigned j = x >> n;
x = i | j;
}
void shift_2(int &x, int n)
{
n &= 0x1f; // 对32取余的另一种方式
x = (x << (INTSEPR-n)) | (x >> n);
}
高低位交换
高低位交换便是循环移位的简单版本，用上题的方法一句话便可实现。
x = (x << 16) | (x >> 16);
╝①
小结
看到这里应该对二进制或者位运算基本的运算和变形都没有问题，还包括了高级运算的位运算的求解，更有涉及C++类的相关操作，希望能对位运算能了然于心。如果你有任何建议或者批评和补充，请留言指出，不胜感激，更多参考请移步互联网。
参考：
①勇幸|Thinking：http://www.ahathinking.com/archives/78.html
②Matrix67：http://www.matrix67.com/blog/
③漫步者×&……%￥：http://www.cppblog.com/Walker/articles/80466.html
④icejoywoo's place：http://www.cnblogs.com/icejoywoo/archive/2012/03/08/2385338.html
相关推荐
二进制运算电路 二进制运算电路 二进制运算电路 数字逻辑 数字逻辑
实验一 二进制算法实现摸指数运算
主要介绍了位运算实现十进制转换为二进制的相关资料,需要的朋友可以参考下
关于二进制的各种运算， 挺不错的 很全了
于是我就开发这个集“位”的各种运算与进制转换的小工具，对于学习C及C++起了很大的帮助，再也不用打开计算器来一个个算了。非常方便，非常人性。 本小工具具备以下功能： 一.位运算相关功能： 1.位与运算 2.位或...
易语言二进制递归运算源码,二进制递归运算,到二进制文本
进行两个四位二进制数的运算。 b.算术运算： A+B,A-B,A+1,A-1。 c.逻辑运算： A and B,A or B,A not, A xor B。 2、4 位输入 A3—A0、B3---B0 用开关设置输入。 3、8种算术逻辑运算通过 3 位功能选择开关选择某一种...
4位同步二进制加法计数器74LS161实验电路multisim源文件，multisim10及以上版本可以正常打开仿真，是教材上的电路，可以直接仿真，方便大家学习。
大数运算包含加，减，乘，除，取模，幂运算，模幂运算。支持十进制运算，二进制运算；支持文件运算，键盘输入运算，若有需要，可提供实验报告
数字系统综合设计，实现四位二进制数逻辑运算和算术运算！
本软件集合了位运算跟进制的转换，简单操作，方便软件工程人员使用，同时也适用于初学c语言的大学生，大学教师使用。
运算基础二进制的运算和计算机中的四则运算.ppt
java二进制运算器（加、见、乘、除）**********
将一个数转化成无符号八位2进制数，将其中的某一位制0或制1
使用C++语言实现十进制转换为二进制的运算方法，可正负互转，解决了上次输出顺序错误的问题
数及其运算 位运算与进制转换-2022.01.02(B).pdf
二进制运算及转换PPT课件.pptx
十六进制数的与或非运算，逻辑运算。支持十六进制数组
十进制转换二进制，八进制，16进制计算小程序