`

位运算的应用

阅读更多
注意:任何语言中二进制是没有显示的表示的,所以如果需要使用二进制则只能用10进制(想成2进制),或者用string
         for(int i=0;i<32;i++){
	Integer a = i|(1<<5);  //100001  ---这里前面5位表示需要增加的东西哦,1<<5,1移动5位,就是移到第六位上
          }
			
  String[] b = Integer.toBinaryString(a).substring(1).split("");
从b[1]----b[5]是真正需要的东西,b[0]为空,因为split("")的原因,这里substring(1)可是把首位截去了哈。。。。

1。与运算
两个二进位均为1时,结果位才为1 ,否则为0

把a 的高八位清 0 , 保留低八位, 可作 a&255 运算 ( 255 的二进制数为0000000011111111)。

应用;
 a. 清零特定位 (mask中特定位置0,其它位为1,s=s&mask)
 b. 取某数中指定位的值 (mask中特定位置1,其它位为0,s=s&mask)
&就像一个橡皮,擦掉0的位,提取1的位
c.a&b<<1 可以看成进位产生的值


2。按位或运算
00001001|00000101
00001101 (十进制为13)可见9|5=13

常用来将源操作数某些位置1,其它位不变。 (mask中特定位置1,其它位为0 s=s|mask) 
|想一根棍子,插入1用的



3。按位异或运算
00001001^00000101 00001100 (十进制为12)
含义是:不进位的加法,又称为半加运算; 1使得特定位置取反
异或运算最本质的意思是找出a和b的不同位,不同位为1

助记:异,1或

应用:
a. 使特定位的值取反 (mask中特定位置1,其它位为0 s=s^mask)
b. 不引入第三变量,交换两个变量的值
c.与自己计算值为0; a^a=0;

4。求反运算

~(0000000000001001)结果为:1111111111110110

5。左移运算符“<<”

其值相当于乘2 。
6。右移运算 ">>"

其值相当于除2。
'下面是从牛逼博客上抄的。。。值得学习'
位运算应用口诀
清零取数要用与,插入某数要用或
若要取反和交换,轻轻松松用异或
  
移位运算
要点 1 它们都是双目运算符,两个运算分量都是整形,结果也是整形。
        2 " < < " 左移:右边空出的位上补0,左边的位将从字头挤掉,其值相当于乘2。
        3 " > > " 右移:右边的位被挤掉。对于左边移出的空位,如果是正数则空位补0,若为负数,可能补0或补1,这取决于所用的计算机系统。
        4 " > > > " 运算符,右边的位被挤掉,对于左边移出的空位一概补上0。
  
位运算符的应用 (源操作数s 掩码mask)
(1) 按位与-- & 
1 清零特定位 (mask中特定位置0,其它位为1,s=s& mask)
2 取某数中指定位 (mask中特定位置1,其它位为0,s=s& mask)
(2) 按位或-- |
      常用来将源操作数某些位置1,其它位不变。 (mask中特定位置1,其它位为0 s=s|mask)
(3) 位异或-- ^
1 使特定位的值取反 (mask中特定位置1,其它位为0 s=s^mask)
2 不引入第三变量,交换两个变量的值 (设 a,b)
 a = a^b^a  //先去到a,b的中间值,然后消去a
 b = a^b^b  //先去到a,b的中间值,然后消去b
以上是简易思路,正确的思路是:先寻找 a和b的不同之处,那么a变成b也就是把他们的相同之处不变,不同之处取反。
异或-----异 和  或:  异:找出不同的地方并置为1
                    或: 碰到1就取反  
这是一个运算符,但可以从两个维度来理解他

应用举例 


(1) 判断int型变量a是奇数还是偶数                      
a& 1    = 0 偶数 (与1相加能进位说明个位是1,个位为0)
a& 1    = 1 奇数 (与1相加不能进位说明个位是0,个位为1)
或者
a&1
判断奇偶也就是判断个位上的数
a = 10010001
b=1
a&b = 0 != b 说明第1位因为是1,所以可进位,所以a的值改变
b=10  a&b = a 说明第二位是0,因为每进位

 a&b = b 说明判断为是0,因为 0&b = b


(2) 取int型变量a的第k位 (k=0,1,2……sizeof(int)),即a> > k& 1 
因为我要取第k位,那么把第k位移到第0位,然后擦掉其他位


(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> > 16-k    (设sizeof(int)=16) 
因为限定是16的循环,那么左移很可能移出去,但是就像地球是圆的一样,从左边跑可以跑到,从右边跑也可以跑到,所以向左移多少就是向右移多少的补 (k+16-k = 16 就是跑了一圈),所以思想是当向左跑跑出界了的话,那么就把向右跑给插入进去吧。。。。

(6) int型变量a循环右移k次,即a=a> > k|a< < 16-k    (设sizeof(int)=16) 

定理1:设a,b为两个二进制数,则a+b = a^b + (a&b)<<1。
证明:a^b是不考虑进位时加法结果。当二进制位同时为1时,才有进位,因此 (a&b)<<1是进位产生的值,称为进位补偿。将两者相加便是完整加法结果。
定理2:使用定理1可以实现只用位运算进行加法运算。
证明:利用定理1中的等式不停对自身进行迭代。每迭代一次,进位补偿右边就多一位0,因此最多需要加数二进制位长度次迭代,进位补偿就变为0,这时运算结束。



(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+(x&y)<<1;
x*2 = x<<1;
x/2 = x>>1;
所以(x+y)/2 = (x^y + x&y<<1)>>1 = x^y>>1 + x&y


512 * 7 = 512 * (4 + 2 + 1) = 512 * 4 + 512 * 2 + 512
= 512 << 2 + 512 << 1 + 51

512/7  因为不能约分,又不是2的倍数,所以除不尽,所以只能近似
512/8 = 512>>3 
 



(8)判断一个整数是不是2的幂,对于一个数 x > = 0,判断他是不是2的幂
boolean power2(int x)
{ 
      return ((x& (x-1))==0)& & (x!=0);
} 
给定一个正整数(N <= 2^32),要求快速判断它是否为2的幂次方。(不可用循环) 
通常我们知道: 
       十进制         二进制 
2^0 == 1              0000 0001 
2^1 == 2              0000 0010 
2^2 == 4              0000 0100 
2^3 == 8              0000 1000 
2^4 == 16             0001 0000 
2^5 == 32             0010 0000 
从上述规律中我们可以得出,题目最终归结为判断此数的二进制表示(unsigned)中是否只有一位为1

因为是2进制,所以x-1会使得低位为1的位及其下面的位置全部错位,而其他高位位不变,这样,这样x&(x-1)将把他们共同的部分保留下来,也就是错位的地方被消除,从而可以消除一个1

x&x-1做一次运算将会消去最低位上的1
所以如果要计算一个数中二进制位1的个数可以这么做
int func(x)
{
    int countx = 0;
    while(x)
    {
        countx++;
        x = x&(x-1);
    }
    return countx;
}

(9) x 的 相反数 表示为 (~x+1) 还不如乘以-1



总结:a&0 ---清零特定位
      a&1 ---保留特定位
      a&b ---保留a和b都是1的位,也就是保留相加的进位
      a&(a-1)---除去最低位的0


分享到:
评论
1 楼 gaoym1020 2011-01-02  
 (8)判断一个整数是不是2的幂,对于一个数 x > = 0,判断他是不是2的幂  
 boolean power2(int x)  
{   
       return ((x& (x-1))==0)& & (x!=0);  
 }

是2的幂的整数具有以下特征:
a)二进制数中,只有一个位为1。如2:0000 0010,4:0000 0100,8:0000 1000
b)x为2的n次幂的数,x-1即为后n位为1的二进制数。如x=8:0000 1000,x-1=7:0000 0111
故,具有*x&(x-1)==0 && x!=0)的数,即为2的幂的数

(9) x 的 相反数 表示为 (~x+1) 还不如乘以-1 
在编程语言中,负数是以补码的方式表示的,也就是通过将与其对应的正数的二进制代码取反(即将1变成0,将0变成1),然后对其结果加1。
例如,-42就是通过将42的二进制代码的各个位取反,即对 00101010 取反得到11010101 ,然后再加1,得到11010110 ,即-42 。

相关推荐

    单片机C51位运算应用技巧

    位运算应用口诀: 清零取位要用与,某位置一可用或,若要取反和交换,轻轻松松用异或! 移位运算要点 1 它们都是双目运算符,两个运算分量都是整形,结果也是整形。 2 "&lt;&lt;" 左移:右边空出的位上补0,左边...

    位运算.pdf

    位运算广泛应用于各种编程领域,尤其是在系统级编程中,例如操作系统开发、网络编程以及硬件控制等方面。下面详细介绍位运算的基本概念及其应用场景。 #### 二、位运算符 C语言提供了多种位运算符来实现对二进制位...

    经典的位运算合集 Matrix67及总结

    【转载】常用位操作 位运算应用口诀 常用位操作 几个常用的位操作 计算树状数组lowbit的三种方法 统计一个整数的二进制中1的个数(位运算技巧) 收藏 统计一个整数的二进制中1的个数的三种方法 位运算讲稿_by_...

    位运算.pdf 精心收集的资料,重新编辑

    3. 位运算应用技巧: - 清零:用`&`操作与掩码进行与运算可以清零特定位。 - 取反:使用异或`^`可以取反某一位,交换两个变量的值。 - 优先级:注意运算符的优先级,如`&`、`|`和`^`低于比较运算符,但高于移位...

    20191220-Java位运算_java_位运算_

    10. **雪花算法中的位运算应用** - 时间戳:通过左移将时间戳的二进制表示放置在高位,例如左移41位,以便容纳69年的时间跨度。 - 工作机器ID:可以分配一部分位作为机器标识,通过位与、位或等运算,确保每个工作...

    位运算简介及实用技巧

    在上述内容中,还提到了一个有趣的位运算应用——无额外变量的交换两个整数(swap)的技巧。通过异或操作,可以实现变量`a`和`b`的值互换,如下所示的Pascal代码: ```pascal procedure swap(var a, b: longint); ...

    位运算及其相关技巧在程序设计的应用

    位运算及其相关技巧在程序设计的应用 位运算是一种在计算机科学和编程中广泛使用的操作,它直接作用于整数在内存中的二进制表示。这种运算不仅速度快,而且在许多场景下能够提供简洁高效的解决方案。本文将深入探讨...

    项目十一 使用位运算.ppt

    7. **位运算应用示例**:例如,给定一个正整数num,要输出其8到11位的数值,可以先右移8位,然后通过按位与运算(与一个特定掩码进行操作)提取出这4位。 在实际编程中,位运算常用于优化算法、节省存储空间、进行...

    单片机位运算PPT学习教案.pptx

    本资源是关于单片机位运算的学习教案,主要介绍了位运算的基本概念、位运算符、位运算应用等知识点。 1. 位运算基本概念 在计算机系统中,位是最小的存储单位,一个字节(Byte)由8个位组成。每个位可以是0或1,...

    Java位运算的应用

    Java中的位运算是一种高效的操作方式,它可以直接对二进制数据进行操作,广泛应用于各种算法和数据处理中。本文将详细介绍这些位运算的应用,并通过具体的例子来解释它们的工作原理。 1. **奇偶数判断**:`a&1`可以...

    ACM位运算技巧

    本篇文章将深入探讨位运算中的各种技巧及其应用场景。 #### 基础位运算符 - **按位与(&)**:如果两个相应的二进制位都为1,则结果位为1;否则为0。 - 清零特定位:利用掩码中特定位置0,其余位为1,通过`&`操作...

    使用位运算计算LOG2

    使用位运算计算LOG2 LOG2是数学中一个常用的函数,用于...使用位运算计算LOG2是一种快速且高效的方法,可以广泛应用于各种领域。通过使用 Magic Number 和哈希表,我们可以快速计算出LOG2值,从而提高计算速度和效率。

    lua进行位运算的文件,直接调用

    在实际应用中,位运算可以用于各种场景,如内存优化、数据编码解码、硬件交互等。例如,你可以使用位运算来创建和检查状态标志,或者在处理二进制数据流时解析特定的位模式。熟悉并熟练运用位运算,可以使你在 Lua ...

    位运算符,位运算,位段

    位运算在操作系统、设备驱动程序、数据压缩、编码解码等场景中有着广泛的应用。例如,它们可用于设置和清除标志位,检查特定状态,以及在有限的位宽内高效存储信息。理解并熟练掌握位运算对于编写高效的C语言程序至...

    位运算使用技巧

    位运算的应用范围广泛,尤其是在编程领域中,它可以用于实现多种功能,包括但不限于: - **数据压缩**:通过位运算可以高效地进行数据压缩和解压。 - **状态管理**:利用位运算可以方便地管理和控制多个布尔状态。 ...

    各种快速位运算算法 算法优化

    本文总结了各种快速位运算算法,涵盖了位运算的基础知识、算法优化技术、实际应用等方面。 位运算基础 位运算是指对二进制数进行的逻辑操作,包括AND、OR、XOR、NOT等。位运算可以用来实现数字信号处理、图形处理...

    位运算大全

    位运算在嵌入式开发、系统编程、算法优化等领域具有重要应用。以下是对位运算的详细说明: 1. **位运算的概念**: 位运算是在数字的二进制表示上进行的运算,例如与(AND)、或(OR)、非(NOT)、异或(XOR)以及...

Global site tag (gtag.js) - Google Analytics