首页
登录 | 注册

Leetcode29-俩数相除 — & (与运算)、|(或运算)、^(异或运算)的本质理解

位与运算符(&)

参加运算的俩个数据,按二进制位进行"与"运算。
运算规则:0&0=0; 0&1=0; 1&0=0; 1&1=1;
即:俩位同时为"1", 结果才为“1”, 否则为0
例如:3&5 即 0000 0011 & 0000 00101 = 0000 0001 因此,3&5的值得1。

另为,负数按补码形式参加位与运算。
其中,正数的补码等于原码;负数的补码等于反码加1,而反码等于原码符号位不变,其余各位取反。

“与运算”的特殊用途:
(1)清零。如果想将一个单元清零,即使其全部二进制位为0, 只要与一个各位都为零的数值相与,结果为零。
(2)取一个数的指定位
方法:找一个数,对应X要取的位,该数的对应位为1,其余位为零,此数与X进行“与运算”可以得到X中的指定位。
例:设X=1010 1110
取X的低4位,用X&0000 1111=0000 1110即可得到;
还可以用来取X的2、4、6位。

位或运算(|)

参与运算的俩个对象,按二进制位进行“或”运算。
运算规则: 0|0=0; 0|1=1; 1|0=1; 1|1=1;
即参与运算的俩个对象只要有一个为1, 其值为1。
例如 3|5, 即0000 0011 | 0000 0101= 0000 0111,因此,3|5的值得7。

另,负数按补码形式参加按位或运算。
“或”运算的特殊作用:
(1) 常用来对一个数据的某些位 置1。
方法:找到一个数,对应X要置1的位,该数的对应位为1,其余位为零。此数与X相或可使X中的某些位置为1。例如:将X=1010 0000的低四位置1,用X|0000 1111 = 1010 1111即可得到。

异或运算符(^)

参加运算的俩个数据,按二进制位进行“异或运算”。
运算规则: 0^0=0; 0 ^1=1; 1 ^ 0 =1; 1 ^ 1=0;
即:参与运算的俩个对象,如果俩个相应位为"异"(值不同),则该结果为1, 否则为0。

“异或运算”的特殊作用:
(1) 使特定位翻转一个数,对应X要翻转的位,该数的对应位为1,其余位为零,此数与X对应位异或即可。
例如X=1010 1110,使低4位翻转,用X^ 0000 1111 = 1010 0001即可得到。

(2)与0相异或,保留原值,X ^ 0000 0000 = 1010 1110
从上面例题可以清楚的看到这一点。

取反运算符 (~)

参加运算的一个数据,按二进制进行“取反”运算。
运算规则: ~1=0 ; ~0=1;
即对一个二进制数按位取反,即将0变1,1变0;

使一个数的最低为为零,可以表示为:a & ~1
~1的值为 1111 1111 1111 1110,再按"与"运算,最低位一定为0。因为“ ~”运算符的优先级比算术运算符、关系运算符、逻辑运算符和其他运算符都高。

左移运算符(<<)

将一个运算对象的各二进制位全部左移若干位(左边的二进制位丢弃,右边补0)。
例:a=a<<2 将a的二进制位左移2位,右补0,
左移1位后a=a*2;
若左移时舍弃的高位不包含1,则每左移1位,相当于该数乘以2。

右移运算符 (>>)

将一个数的各二位进制位全部右移若干位,正数左补0, 负数左补1,右边丢弃。
操作数每右移一位,相当于该数除以2。
例如:a=a>>2 将a的二进制位右移2位,左补0 或者 左补1得看被移数是正还是负。

&gt;&gt;&gt;&gt; 运算符把 expression1 的所有位向右移 expression2 指定的位数。expression1的符号位被用来填充右移后左边空出来的位。向右移出的位被丢弃。

例如,下面的代码被求值之后,temp的值是 -4;
-14 (14的二进制为 0000 1110, 14的反码为1111 0001, -14的二进制码为1111 0010)右移俩位等于-4 (移动后的二进制码为1111 1100, 移动后的反码为1111 1011, 移动后的原码为0000 0100, 即为4)

无符号右移运算符 (>>>)

&gt;&gt;&gt;&gt;&gt;&gt; 运算符把expression1 的各个位向右移expression2指定的位数。右移后左边空出的位用零来填充。移出的右边的位被丢弃。
例如: var temp=-14 >>> 2
变量 temp的值为-14 (11111111 11111111 11111111 11110010 ), 向右移俩位后等于 1073741820 (即二进制的 00111111 11111111 11111111 11111100)

复合运算符

位运算符与赋值运算符结合,组成新的赋值运算符,它们是:
&= 例: a &=b 相当于a=a&b (与运算)
|= 例: a |= b 相当于 a=a|b   (或运算)
&gt;&gt;=&gt;&gt;= 例:a>>=b 相当于 a= a>>b (右移运算符)
&lt;&lt;=&lt;&lt;= 例:a<<=b 相当于 a=a<<b (左移运算符)
^= 例:a ^ =b 相当于a=a ^ b (异或运算符)
运算规则:和前面讲的符合赋值运算符的运算规则相似。

不同长度的数据进行位运算:
如果俩个不同长度的数据进行位运算时,系统会将俩者按右端对齐,然后进行按位计算。
在C语言中,long 占4个字节,即32位,如果一个long型数据与一个int型数据进行"与"运算的话,右端对其后,左边不足的位依下面三种情况补足:
(1) 如果整型数据为正数,左边补16个0;
(2) 如果整型数据为负数,左边补16 个1;
(3) 如果整型数据为无符号数,左边也补16个0;

如: long a=123; int b=1; 计算a&b
long a=123; int b=-1; 计算a&b
long a=123; unsigned int b=1; 计算a&b

附:C/C++基本数据类型所占字节数

INT_MAX, INT_MIN数值大小

因为int 占字节32位,根据二进制编码的规则,INT_MAX=2^31-1, INT_MIN=-2 ^31. 在C/C++ 中,所有超过该限值的数,基本上都会溢出,出现warning, 但是并不会出现error。如果想表示的整数超过了该限值。可使用长整型long long占8位字节64位来表示。

关于INT_MAX 和 INT_MIN的运算

由于二进制编码按原码,补码和反码的规则,所有程序中对INT_MAX和INT_MIN的运算应当格外注意,在出现溢出的时候,不遵循数学规则。
INT_MAX+1=INT_MIN
INT_MIN-1=INT_MAX
abs(INT_MIN)=INT_MIN
比较有趣的是:INT_MAX+1<INT_MAX; INT_MIN-1>INT_MIN; abs(INT_MIN)<0;

Leetcode-29 俩数相除
给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:
输入: dividend = 10, divisor = 3
输出: 3

示例 2:
输入: dividend = 7, divisor = -3
输出: -2

说明:
•被除数和除数均为 32 位有符号整数。
•除数不为 0。
•假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231 − 1]。本题中,如果除法结果溢出,则返回 231 − 1。

解法1:通过不断循环求被除数与除数的商,当被除数和除数相差很大的时候,会超时。

class Solution {
public:
    int divide(int dividend, int divisor) {
        /*
        if(dividend==INT_MIN && divisor==-1) return INT_MAX;
        //if(divisor==0) return INT_MAX;
        long m=abs((long) dividend);                                  //long long为8位数据类型
        long n=abs((long) divisor);
        int res=0;
        while(m>=n){  //循环遍历
            long t=n; 
            long p=1; //其中res为商,p为计数器,其中计数器的作用是统计这次的商
            if(m>(t<<1)){
                t=t<<1;
                p=p<<1;
            }
            m-=t;
            res+=p;
        }
        if((dividend < 0) ^ (divisor < 0)) res=-res;
        return res>INT_MAX? INT_MAX:res;
     }
 }

解法2: 通过递归求被除数与除数的商,代码更为简单,不会超时。

class Solution {
public:
    int divide(int dividend, int divisor) {
        long long res = 0;
        long long m = abs((long long)dividend), n = abs((long long)divisor);
        if (m < n) return 0;
        long long t = n, p = 1;
        while (m > (t << 1)) {
            t <<= 1;
            p <<= 1;
        }
        res += p + divide(m - t, n); //递归
        if ((dividend < 0) ^ (divisor < 0)) res = -res;
        return res > INT_MAX ? INT_MAX : res;
    }
};


2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.009 s.
京ICP备10005923号