计算机组成原理

Posted by lily's blog on December 7, 2024

二进制位计算

在计算机中 a&b 表示a与b进行按位与运算, 逐一比较两个数的二进制位,如果两个比特都是1,该位结果为1,否则为0。 在二进制中 x & 1,等价于检查数字的最低为是否为1(最右边的位)(因为1的二进制数为1)。 而在二进制到十进制的转换中,由于最右的数为 x*2_0,2_0=1,因此奇数可以表示为2k+1,偶数可以表示为2k

**根据每个二进制位的位置**来计算其对应的十进制值。每一位上的数字与该位对应的 `2` 的幂相乘,然后将结果相加。
1. 从右到左,记住每一位的权重是 `2^0, 2^1, 2^2, ...`。
2. 每一位上的数字与对应的幂次的 `2` 相乘。
3. 将所有结果相加,得到十进制值。

所以在二进制数中,最低位为1表示当前数为奇数 例如: 1的二进制数为1 3的二进制数为11 5的二进制数为101。

向下取整改为向上取整

事实上,我们可以修改这个下取整的行为,让它上取整。上面这两种情况就可以统一起来,在计算左边元素个数的时候,可以用一个统一的式子,即:

(len(num1)+len(nums2)+1)/2 ​

这里用到了一个小技巧,把下取整,修改为上取整的时候,只需要在被除数的部分,加上除数减 1 即可,这里除数是 2 ,因此被除数加 1 即可。大家可以自行验证一下,就拿我们上面举出的例子来验证一下这个事实:

当 len(nums1) = 5、len(nums2) = 5 的时候,

(len(num1)+len(nums2)+1)/2=5; 当 len(nums1) = 4、len(nums2) = 5 的时候,

(len(num1)+len(nums2)+1)/2=5,左边比右边多一个元素。