二进制位的应用

淡淡的烟草味﹌ 2022-07-16 03:39 211阅读 0赞

# 问题1 #

100瓶药水中有且仅有1瓶有毒，小白鼠喝毒药后24h内死亡。要在24h内查出有毒药瓶，至少需要多少只鼠？

# 思路 #

使用100只老鼠一定可以检测出哪瓶药有毒，分别给100只老鼠编号从1到100，并且给100瓶药编号从1到100；那么编号为1的老鼠喂编号为1的那瓶药，编号为2老鼠喂编号为2瓶药，…., 编号为100的老鼠喂编号为100的那瓶药。24小时过后，查看编号几的老鼠死亡，则编号为几的那瓶药有毒（老鼠和药的编号是一一对应的）。

## 改进思路 ##

如果编号为100的那瓶药不喂给编号为100的老鼠，那么也可以得到结果。如果前99只老鼠都没有死亡，那么编号为100的那瓶药肯定有毒，如果前99只老鼠有一只死亡，那么其对应编号的那瓶药就有毒，所以可以使用99只老鼠来检测100瓶药哪瓶药有毒。

## 怎么减少老鼠的数量来解决问题 ##

### 思考 ###

--------------------

一个常见的二进制问题：

用4位可以表示0~7这8个数字 ，8位可以表示0~255这256个数字。

同理，使用7只老鼠就可以表示0~127这128瓶编号的药，其中每只老鼠编号为0~6，且老鼠被喂药则用1表示，不喂药用0表示。

000 0000 表示编号为0的药没有喂给任何老鼠  
000 0001 表示编号为1的药喂给编号为0的老鼠  
000 0010 表示编号为2的药喂给编号为1的老鼠  
……  
110 0011 表示编号为99的药喂给了编号为0、1、5、6的老鼠  
110 0100 表示编号为100的药喂给编号2、5、6的老鼠

最后，如果这7只老鼠在24小时后的死亡后，其二进制编码表示的数就对应着这个编码的药是毒药。

--------------------

举例：

若第99瓶药是毒药，那么编号为0、1、5、6这四只老鼠会死亡，那么对应的二进制编码为110 0011，刚好对应着第99瓶药喂药老鼠的编号所组成的二进制编码。

--------------------

# 问题2 #

不使用”+”、”/”、”\*”求100\*n的值

## 解题思路 ##

二进制凑十进制的100

long long getRes(int n) {
        // 100*n = 128*n - 16*n - 8*n - 4*n 
        return (n << 7) - (n << 4) - (n << 3) - (n << 2);
    }

--------------------

# 问题3 #

不用乘法，除法，取模的方式求两个整数的商  
[Divide Two Integers][]

## 原理解释 ##

**符号的确定**  
除数与被除数符号决定了商的符号  
同为正或负，(divident < 0)^(divisor < 0) 结果为0  
一正一负，(divident < 0)^(divisor < 0) 结果为1

**整数最大值和最小值问题的处理**  
1. 使用更大的范围来表示数值：long long  
2. 使用labs求整数最小值的绝对值

**算法的核心**  
所有的整数都可以用二进制表示  
如：7 = 2^2 + 2^1 + 2^0

**处理核心**: 移位+做差

int divide(int dividend, int divisor) {
        if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) return INT_MAX;
    
        if (dividend == INT_MIN && divisor == 1)  return dividend;
    
        int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
    
        long long dvd = labs(dividend);
        long long dvs = labs(divisor);
        int res = 0;
        while (dvd >= dvs) {
            long long tmp = dvs, multiple = 1;
            while (dvd >= (tmp << 1)) {
                tmp <<= 1;
                multiple <<= 1;
            }
            dvd -= tmp;
            res += multiple;
        }
    
        if (sign == -1) {
            res = -res;
        }
        return res;
    }

# 问题4 #

不用算数运算符求和

## 分析 ##

要求不能用算数运算符，那么只能考虑可用的的位操作符

![这里写图片描述][20161113200749161]

## 代码 ##

int sum(int a, int b) {
        if (b == 0) return a;
        // a^b 没有进位的加法
        int c = a ^ b;          
        // a&b a与b相加后各个位置向高位进位
        int d = (a & b) << 1;
    
        // 依次求得每一位加上进位后的数值 
        return sum(c, d);  
    }

## 模拟样例 ##

7+9 = ?

c = a ^ b = 0111 ^ 1001 = 1110  
d = (a & b)<< 1= (0111 & 1001) << 1= 0001 << 1 = 0010

c = a ^ b = 1110 ^ 0010 = 1100  
d = (a & b) << 1 = (1110 & 0010) << 1 = 0010 << 1 = 0100

c = 1100 ^ 0100 = 1000  
d = (1100 & 0100) << 1 = 0100 << 1 = 1000

c = 1000 ^ 1000 = 0000  
d = (1000 & 1000) << 1 = 1000 << 1 = 10000

c = 0000 ^ 10000 = 10000  
d = (0000 & 10000) << 1 = 0000 << 1 = 0000

[Divide Two Integers]: https://leetcode.com/problems/divide-two-integers/
[20161113200749161]: /images/20220716/7fbea85998c64d46be60805afdf625aa.png