澳门正规赌博十大网站-澳门游戏网站
做最好的网站

位运算小结,位运算符及其应用

位运算小结,位运算符及其应用。5、获得最小的int值

与获得最大的int方法类似。

 

/*
 求最小int
 得到结果:-2147483648
*/
int getMinInt()
{
 return 1 << 31;
}

/*
 同样在g  下编译,出现warning: left shift count is negative
*/
int getMinInt_2()
{
 return 1 << -1;
}

 

6. 右移运算

右移运算符“>>”是双目运算符。右移n位就是除以2的n次方

其功能是把“>>”左边的运算数的各二进位全部右移若干位,“>>”右边的数指定移动的位数。

例如:设 a=15,a>>2 表示把000001111右移为00000011(十进制3)。

应该说明的是,对于有符号数,在右移时,符号位将随同移动。当为正数时, 最高位补0,而为负数时,符号位为1,最高位是补0或是补1 取决于编译系统的规定。Turbo C和很多系统规定为补1。

右移对符号位的处理和左移不同:

对于有符号整数来说,比如int类型,右移会保持符号位不变,例如:

int i = 0x80000000;

i = i >> 1;  //i的值不会变成0x40000000,而会变成0xc0000000

位运算小结,位运算符及其应用。就是说,对于有符号数, 符号位向右移动后,正数的话补0,负数补1,

对于有符号数,在右移时,符号位将随同移动:

当为正数时, 最高位补0,

而为负数时,符号位为1,

也就是汇编语言中的算术右移.同样当移动的位数超过类型的长度时,会取余数,然后移动余数个位.

位运算小结,位运算符及其应用。最高位是补0或是补1 取决于编译系统的规定。Turbo C和很多系统规定为补1。

负数10100110 >>5(假设字长为8位),则得到的是  11111101

总之,在C中,左移是逻辑/算术左移(两者完全相同),右移是算术右移,会保持符号位不变.实际应用中可以根据情况用左/右移做快速的乘/除运算,这样会比循环效率高很多. x>>1;   //相当于 x /= 2x<<1;   //相当于 x *= 2x>>2;   // x /=4x<<2;   // x *= 4x>>3;   // x /= 8x<<3;   // x *= 8以此类推.

无符号:

main(){
    unsigned a,b;
    printf("input a number: ");
    scanf("%d",&a);
    b=a>>5;
    b=b&15;
    printf("a=%dtb=%dn",a,b);

}

请再看一例!

main(){
    char a='a',b='b';
    int p,c,d;
    p=a;
    p=(p<<8)|b;
    d=p&0xff;
    c=(p&0xff00)>>8;
    printf("a=%dnb=%dnc=%dnd=%dn",a,b,c,d);
}

 

 

leetcodeBIT相关题目bit manipulation

位运算常用技巧总结(01),运算技巧总结01

1.   按位与运算

按位与运算符"&"是双目运算符。

        其功能是参与运算的两数各对应的二进位相与。只有对应的两个二进位均为1时,结果位才为1 ,否则为0。参与运算的数以补码方式出现。

例如:9&5可写算式如下: 00001001 (9的二进制补码)&00000101 (5的二进制补码) 00000001 (1的二进制补码)可见9&5=1。

         按位与运算通常用来对某些位清0或保留某些位。例如把a 的高八位清 0 , 保留低八位, 可作 a&255 运算 ( 255 的二进制数为0000000011111111)。

 

main(){
    int a=9,b=5,c;
    c=a&b;
    printf("a=%dnb=%dnc=%dn",a,b,c);
}

与2的次方相乘相除

public class Temp {
    public static void main(String[] args) {
        int a = 16;
        System.out.println(a >> 1); // devide by 2^1
        System.out.println(a << 1); // mutiple by 2^1
        System.out.println(a >> 3); // devide by 2^3
    }
}

2、判断一个数是否是2的n次方

一个数是2的n次方,则这个数的最高位是1,其余位为0。根据上一题的第二种解法可以很容易得到解决方案。将这个整数与整数减一进行与运算,如果得到的结果为零,可证明该数为2的n次方。

 

/*
 判断一个数是否为2的n次方(一个数为2的n次方,则最高位为1,其余位为0)
*/
bool is2Power(int num)
{
 bool flag = true;

 num = num & (num - 1); //计算num和num - 1的与的结果
 if(num) //如果结果为0,则不是2的n次方
 {
  flag = false;
 }

 return flag;
}

位运算小结,位运算符及其应用。 

一、C语言的六种位运算符:

& 按位与

| 按位或

^ 按位异或

~ 取反

<< 左移

>> 右移

 

位运算小结,位运算符及其应用。位运算应用

11、求解倒数第m位相关问题

 

/*
 获取n的倒数第m位的值(从1开始计数)
*/
int getMthByTail(int n,int m){
 return (n >> (m - 1)) & 1;
}

/*
 将n的倒数第m位设为1
*/
int setMthByTail21(int n,int m)
{
 return n | (1 << (m - 1));
}

/*
 将n的倒数第m位设为0
*/
int setMthByTail20(int n,int m)
{
 return n & ~(1 << (m - 1));
}

 

基础知识 对于 位运算 ,大家都很熟悉,基本的位操作有与()、或(||)、非(!)、异或()等等。在面试...

位运算小结,位运算符及其应用。二、异或操作的妙用

1. 使特定位翻转     要使哪几位翻转就将与其进行∧运算的该几位置为1即可。

2 与0相∧,保留原值.

3.交换两个值,不用临时变量.

我们可以在不用引入其他变量就可以实现变量值的交换

用异或操作可以实现:

      a = a^b;          //(1)
      b = a^b;          //(2)
      a = a^b;          //(3)

异或操作满足结合律和交换律,且由异或操作的性质知道,对于任意一个整数a^a=0;

证:(第(2)步中的a) a = a^b =(将第(1)步中的b代入b) a^(a^b) = b;

(第(3)步中的b)b =a^b = (将第(1)步中的b代入b,将第(2)步中的a代入a) a^b^a^a^b = a^a^a^b^b = a;

 

三 、位与运算

1 . 清零      A数中为1的位,B中相应位为0。然后使二者进行&运算,即可达到对A清零目的。

2 . 取一个数中某些指定位 取数A的某些位,把数B的某些位置1,就把数A的某些位与1按位与即可。

3 . 保留一位的方法     数A与数B进行&运算,数B在数A要保留的位1,其余位为零。

4 .  判断奇偶性 将变量 a的奇偶性。a与1做位与运算,若结果是1,则 a是奇数;将 a与1做位与运算,若结果是0,则 a是偶数。

4、应用举例

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>>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,但是我们知道它们的平均值是肯定不会绯龅模颐怯萌缦滤惴ǎ?/DIV>

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;
}

php:
$a ='dd';
$b = 'bb';

$a = $a ^ $b;
$b = $a ^ $b;
$a = $a ^ $b;
echo $a,' ', $b;

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  ( a  & log2(2))      
       a % 4 等价于 a & 2  ( a  & log2(4))  **

      .....       
       a % 32 等价于 a & 5


**
15** if (x == a) x= b;
    else x= a;
 等价于 x= a ^ b ^ x;

16 x 的 相反数 表示为 (~x 1)

判断某个数是否是2的次方

如果某个数是2的次方,则这个数的二进制形式‘1’的个数为1,即1,10,100,1000等形式。

public class Temp {
    public static void main(String[] args) {
        int a = 16, b = 15;
        // use n&(n-1)==0&n>0
        System.out.println(a > 0 && (a & (a - 1)) == 0);
        System.out.println(b > 0 && (b & (b - 1)) == 0);
    }
}

或者使用数学方法

public class Temp {
    public static void main(String[] args) {
        int a = 16, b = 15;
        System.out.println((int) (Math.pow(2, 30)) % a == 0);
        System.out.println((int) (Math.pow(2, 30)) % b == 0);
    }
}

数学方法可以推广到3的次方,4的次方,数学定理

2^m 可以整除2^n (m>n)

8、交换两个数(不借助第三变量)

4. 求反运算

求反运算符~为单目运算符,具有右结合性。

       其功能是对参与运算的数的各二进位按位求反。

例如~9的运算为: ~(0000000000001001)结果为:1111111111110110

 

求绝对值

  1. 先移位来取符号位,int i = a >> 31; 要注意如果 a 为正数,i 等于 0,为负数,i 等于 -1。然后对i进行判断——如果i等于0,直接返回。否之,返回~a 1。
public class Temp {
    public static void main(String[] args) {
        int a = 16, b = -15;
        System.out.println((a >> 31) == 0 ? a : ~a   1);
        System.out.println(b >> 31 == 0 ? b : ~b   1);
    }
}
  1. 对于任何数,与 0 异或都会保持不变,与 -1 即 0xFFFFFFFF 异或就相当于取反(注意,计算机表示使用补码表示)。因此,a 与 i 异或后再减 i(因为 i 为 0 或 -1,所以减 i即是要么加 0要么加 1)也可以得到绝对值。所以可以对上面代码优化下:
public class Temp {
    public static void main(String[] args) {
        int a = 16, b = -15;
        int i = a >> 31;
        System.out.println((a ^ i) - i);
        int j = b >> 31;
        System.out.println((b ^ j) - j);
    }
}

本文由澳门正规赌博十大网站发布于澳门游戏网站,转载请注明出处:位运算小结,位运算符及其应用