有符号数的运算
了解完前置知识,接下来我们举几个例子来看下有符号数是如何进行运算的。
左移运算符
<<
称为左移运算符,它的运算规则为:
- 移除二进制数最高位的0
- 在二进制数的末尾补上一个0
我们以01010000
为例,假设他的字长为32位(多余的0省略),对其左移一位,它的运算过程如下图所示:
image-20211030191646272
左移1位后,我们计算出来的结果为:010100000
,转换成十进制后结果为2^5 + 2^7 = 32 + 128 = 160
。
01010000
的十进制数为80
,左移动1位后,值变为了160
,经过观察后,我们发现左移后的值正好是原值的2倍,等价于乘2操作。
大多数情况下我们可以将其当作乘2使用,但在一些特殊情况下它并不代表真正的乘2,例如,我们需要将其左移25位,如下图所示(我们把省略的0补上):
image-20211030191558946
左移25位后,我们发现它左侧的0已被删完,最高位变成了1,这个数也从原来的正数,变为了负数。如果我们左移26位,左侧的0不够,会开始从右侧取值,最终的值又变成了正数。
因此,我们会发现这样一条规律:
- 当左移的位数,超过剩余字长时,它的值并非乘2
注意:如果任意一个二进制数,左移的位数大于等于字长(例如字长为32,我们左移32位,右边补32个0),那么与之对应的十进制数岂不是都为0了?
当然不是,二进制数进行左移时,当移动的位数大于等于它的字长时,位数会先求余数,然后再进行左移。
例如:我们需要对一个字长为32位的二进制数进行左移32位,那么就需要先求它的余数,即:
32 % 32 = 0
,需要左移0位。左移33位的值和左移1位是一样的。
image-20211030192330358
右移运算符
>>
称为右移运算符,它的运算规则分为正数与负数两种情况。
正数:
移除最低位的数,在最高位补0。
我们以01010000
为例(十进制值为80),对其右移4位,计算过程如下图所示:
image-20211030221935067
计算出来的二进制结果为
00101
,将其转位十进制,结果为:2^0 + 2^2 = 1 + 4 = 5
,即:80 >> 4 = 5
我们用计算器来验证下:
image-20211030225942888
负数:
经过前面的学习,我们知道了负数是以原码的补码形式存储的,它的右移规则为:
- 对补码进行右移,在最高位补1
- 求出其反码
- 对反码+1,求出原码
我们以
10110000
为例(十进制为-80
),将其右移4位,计算过程如下所示:
image-20211030231644452
计算出来的二进制结果为
11100
,我们将其专为十进制:2^0 + 2^2 = 1 + 4 = 5
,补齐符号位,结果为:-5
。即:-80 >> 4 = -1
。
我们用计算器来验证下,如下图所示:
image-20211030231953329
与运算符
&
称为与运算符,它的运算规则为:
- 符号左右两侧的数同时为1,结果就为1,否则为0
即:0 & 0 = 0; 0 & 1 = 0; 1 & 0 = 0; 1 & 1 = 1
接下来,看个十进制的例子,来看下它的运算过程,如下所示:
15 & 13
,它的运算步骤为:
- 将十进制转为二进制
- 对二进制进行与运算
运算过程如下图所示:
image-20211031182434882
或运算符
|
称为或运算符,它的运算规则为:
- 符号左右两侧的数,有一个为1,其值就为1
即:0 | 1 = 1; 1 | 0 = 1; 0 | 0 = 0; 1 | 1 = 1
我们继续以前个章节的数字为例,来看下15 | 13
的运算步骤:
- 将十进制转二进制
- 对二进制进行或运算
运算过程如下图所示:
image-20211031184228354
异或运算符
^
称为异或运算符,它的运算规则为:
- 符号左右两侧的数,值不同,则该位结果为1,否则为0
即:0^0=0; 0^1=1; 1^0=1; 1^1=0
我们继续以15和13为例,看下15^13
的运算步骤:
- 将十进制转二进制
- 对二进制进行异或运算
运算过程如下图所示:
image-20211031202538320
问题求解
有了上述知识做铺垫后,接下来我们进入正题:有一个十进制整数,求它的二进制数中1的个数。
分析
在解决这个问题之前,我们先来分析这样一个场景:
如果一个整数不等于0,那么该整数的二进制表示中至少有一位是1。
先假设这个数的最右边一位是1,那么减去1时,最后一位变成0而其他所有位都保持不变。也就是最后一位相当于做了取反操作,由1变成了0。
接下来,假设这个数最右边的一位是0的情况:
如果该整数的二进制表示中,最右边的1
,位于第m
位,那么减去1时:
- 第
m
位由1变成了0 - 第
m
位之后的所有0都变成1 - 整数中第m位之前的所有位都保持不变
我们举个例子:
一个二进制数01010000
,它的第4位是从最低位数起的第一个1,减去1后:
- 第4位变0
- 它后面的四个0全变1
- 它前面的所有位保持不变
因此得到的结果为01001111
,转成十进制后为79
。
结论
前面我们分析的两种情况中,我们发现把一个整数减去1,都是把最右边的1变成0。如果它的最右边还有0,则所有的0都变成1,而它左边的所有位都保持不变。
接下来,我们把一个整数和它减去1的结果做位与运算,相当于把它最右边的1变成0。我们还是以前面的01010000
为例,它减去1的结果是01001111
。我们再对它们二者进行位与运算,得到的结果是:01000000
。
image-20211031214343399
经过观察后,我们发现:把
01010000
最右侧的1变成了0,结果刚好就是01000000
。
思路与编码
看到这里,我想各位开发者已经看出了此问题的解题思路了🤓。
没错,思路就是:把一个整数减去1,再和原整数做位与运算,会把该整数最右侧的1变成0。
那么,一个整数的二进制表示中有多少个1,就可以进行多少次这样的操作,直至整个数变为0,我们对每一次操作进行计数,就得到了这个问题的答案。
基于这种思路,我们就可以愉快的进行编码了,代码如下所示:
export default class BinaryOperation { /** * 获取二进制中1的个数 * @param decimalVal 十进制数 */ public getBinaryOneNum(decimalVal: number): number { let count = 0; // 十进制数不为0,代表其二进制表示中仍存在1 while (decimalVal !== 0) { // 二进制中所存在的1的总数+1 count++; // 对十进制数与其-1后的数进行位与运算 // 得出结果后替换原十进制数,进行下一轮计算,直至十进制数为0 decimalVal = decimalVal & (decimalVal - 1); } // 返回结果 return count; } }
最后,我们写个测试用例,验证下上述代码能否正常工作,如下所示:
import BinaryOperation from "../BinaryOperation.ts"; const binaryOperation = new BinaryOperation(); const result = binaryOperation.getBinaryOneNum(80); const result2 = binaryOperation.getBinaryOneNum(-80); console.log(`80的二进制表示中有${result}个1`); console.log(`-80的二进制表示中有${result2}个1`);
运行结果如下图所示:
image-20211031215022229
示例代码地址:BinaryOperation.ts、BinaryOperation-test.ts
运行结果与我们手动算出来的二进制数中1的个数一致😋
-80
我们在前面的章节中算过它的二进制表示为10110000
,我们讲过二进制具体在计算机中占多少位,取决于它的字长,我们在书写时只需要标明它的符号位,高位上多出的1可以省略。此处,我们算出
-80
的二进制表示中有27个1,我们加上此处的5个0,可以知道它的字长为27 + 5 = 32
。
写在最后
至此,文章就分享完毕了。
我是神奇的程序员,一位前端开发工程师。
如果你对我感兴趣,请移步我的个人网站,进一步了解。
- 公众号无法外链,如果文中有链接,可点击下方阅读原文查看😊