运算符¶

逻辑运算符¶

运算符	说明
a && b	逻辑与
a \|\| b	逻辑或
! a	逻辑非

位运算符¶

虽然计算机要求程序员以字节为单位进行操作，但是底层代码到处都是16进制和位运算操作符，位运算符操作单个比特。

void do_something(uint8_t *data, size_t len, uint8_t key) {
    for (size_t i = 0; i < len; i++) {
        uint8_t x;
        uint8_t left;
        uint8_t right;
        uint8_t rot;

        x = (uint8_t)(data[i] ^ key);
        left = (uint8_t)(x << 3);
        right = (uint8_t)(x >> 5);

        rot = (uint8_t)(left | right);
        data[i] = rot;
    }
}

在最底层的硬件层面，所有功能都必须要通过物理连接来实现。正因如此，中央处理器被设计为同时处理特定数量的比特。

例如：16位处理器就是为处理16位数据块而设计的。

如果我们要相加两个24位数，该处理器就无法一步完成运算，它需要把工作拆分成两步进行。

如果要相加两个8位数就无需专门的8位电路，处理器直接使用16位加法器，将闲置位填0即可。

处理器一次可处理的比特数就是我们所说的字“word”，在计算领域，“字”是处理器的原生数据单位，指令集和硬件都针对这种固定大小的数据块作为单一单元进行优化，这就是为什么几乎没有计算机能用常规算数运算直接操作单个比特。因为没有专门设计用于单个比特运算的电路。

中央处理器会同时处理整个字，但结果中的每个比特都是独立计算的，仅取决于输入字中的对应比特。

按位与（ & ）¶

对两个数的比特位进行合并，只有当这两个数都是 1 的时候才能返回 1。

Input1：1 1 1 1 1 1 0 0

Input2：0 0 1 1 1 1 1 1

result： 0 0 1 1 1 1 0 0

按位或（ | ）¶

对两个比特位进行比较，只要两个操作位任意一个为 1 时，那么对应的位数就为 1。

Input1：1 0 1 1 0 0 1 0

Input2：0 1 0 1 1 1 1 0

result： 1 1 1 1 1 1 1 0

按位非（ ~ ）¶

对所有位的数字进行取反操作。

输入：0 0 0 0 1 1 1 1

输出：1 1 1 1 0 0 0 0

按位异或（ ^ ）¶

或者说“互斥或”可以对两个数的比特位进行比较，当两个操作数的对应位不相同时，该数的对应位就为 1 。

Input1：0 0 0 1 0 1 0 0

Input2：0 0 0 0 0 1 0 1

result： 0 0 0 1 0 0 0 1

位移运算符¶

位左移运算符（ << ）和位右移运算符（ >> ）可以把所有位数的数字向左或向右移动一个确定的位数。位移时一个比特会被移出，同时在另一侧需要补入新比特（可以补0，可以补1，可以补移出的位“循环位移”）。

位左移和右移具有给整数乘以或除以二的效果。将一个数左移一位相当于把这个数翻倍，将一个数右移一位相当于把这个数减半。

原数：100 = 4

右移：10 = 2

左移：1000 = 8

//利用位移，8字节对齐。
int func0(int x)
{
    //    return (x + 7) / 8 * 8;//等于下面这行
    return (x + 7) >> 3 << 3;//先往右 再往左
}

int a = func0(50);
NSLog(@"a:%d",a);//输出56

位运算符经典算法¶

交换变量的值¶

var a = 10
var b = 8
a = a ^ b//a的值变成了a和b不同位的记录
b = a ^ b//此时b的值变成了a
a = a ^ b//此时a的值变成了b
print(a,b)

成对数字中缺失的数字¶

如果是相等的两个数“异或”，得到的结果为 0 。而 0 与任何数字“异或”，得到的是那个数字本身。

所以将所有的数字做“异或”操作，因为只有一个数字消失，那么其他两两出现的数字“异或”后为 0 ，0 与仅有的一个的数字做“异或”，就得到了消失的数字。

func findLostNum(nums: [UInt]) -> UInt {
    var lostNum: UInt = 0
    for num in nums {
        lostNum = lostNum ^ num
        print(lostNum)
    }
    return lostNum
}

print(findLostNum(nums: [1, 1, 2, 3, 4, 3, 2, 4, 5]))

如果有两个数字意外丢失了（丢失的不是相等的数字），该如何找到丢失的两个数字？

思路：

设题目中这两个只出现 1 次的数字分别为 A 和 B，如果能将 A，B 分开到二个数组中，那显然符合“异或”解法的关键点了。因此这个题目的关键点就是将 A，B 分开到二个数组中。

由于 A，B 肯定是不相等的，因此在二进制上必定有一位是不同的。根据这一位是 0 还是 1 可以将 A 和 B 分开到 A组和 B组。而其它成对的数字要么两个都属于 A 组，要么两个都属于 B 组。再对 A组和 B组分别执行“异或”解法就可以得到 A，B 了。而要判断 A，B 在哪一位上不相同，只要根据 “A 异或 B” 的结果就可以知道了，这个结果在二进制上为 1 的位都说明 A，B 在这一位上是不相同的。

func findTwoLostNum(nums: [UInt]) -> (UInt, UInt) {
    var lostNum1: UInt = 0
    var lostNum2: UInt = 0
    //1. 找到缺失的两个数 异或 的结果
    var temp: UInt = 0
    for num in nums {
        temp = temp ^ num
    }
    //2. 找到第一个为1的位，类似掩码
    var flag: UInt = 1
    while ((flag & temp) == 0) {
        flag = flag << 1
    }
    //找两个丢失的数字
    for num in nums {
        if flag & num == 0 {//A组 结果为0的一组
            lostNum1 = lostNum1 ^ num
        } else {                        //B组 结果为1的一组
            lostNum2 = lostNum2 ^ num
        }
    }
    return (lostNum1, lostNum2)
}

print(findTwoLostNum(nums: [1, 1, 2, 3, 3, 2, 4, 6]))

存储空间问题¶

在二进制中表示布尔值只需1比特，单个比特正好能存储两种状态：1或0。内存和存储硬件并不以比特为单位运作，最小的可寻址单位是1字节（byte），即8比特（bit）构成的组。

中央处理器CPU存取数时，必须提供内存地址，而该地址始终指向完整的一个字节。不存在直接读取第3比特或写入第5比特的指令。内存操作总是以整个字节为单位进行。因此，编程语言定义的基础数据类型最小单位为1字节。所以声明布尔变量时，通常会占用整个字节存储，尽管只用了1比特，剩余的7比特就被浪费了。

优化：¶

不再用完整布尔值存储每个开关，而是用每位代表一个开关状态，将8个开关状态压缩到一个字节中。此时位运算便能大显身手。这种将多个值压缩存储在一个字节中的技术被称为比特打包。

先定义4个高层操作：¶

所有操作都接收一个字和一个数字n，字内的比特索引总是从0开始，意味着最低有效位时第0位，最高有效位是第7位。

当n等于3时，表示的是第4个比特位。

set()置位¶

由于我们无法直接修改字中的单个比特位，因此若要将第n位的比特设置为1，需要对整个字进行操作，保持其它比特不变，仅使目标比特变为1。

操作方法：创建一个掩码（除了第n位为1外，其余位全为0），然后对原始字和掩码按位或运算。

每个比特位置都需要不同的掩码，手动输入会很繁琐，为了将这个流程通用化，可以这样做：

从数字1（二进制00000001）开始，然后将其向左移动n次。例如：要获取位置等于4的掩码，就向左移动4次，就得到想要的掩码。

通常来说，要设置一个比特位，我们将数字1向左移动n个位置（mask = 1 << n），然后将这个掩码与原值进行或运算。

void set(uint8_t *word, uint8_t n) {
    *word = *word | (1u << n);
}

clear()清零¶

类似的思路，由于我们无法直接修改字中的单个比特位，需要用要一个掩码来强制将第n位变为0，同时保持其它位不变。

如果要清除的位置n等于1，掩码对应位置需要是0，其余位置全为1，对字和掩码进行按位与运算。

通用掩码的构建方法是：始于数字1，左移至目标位置，再执行按位取反运算使所有比特翻转。mask = ~(1 << n)

void clear(uint8_t *word, uint8_t n) {
    *word = *word & ~(1u << n);
}

toggle()翻转¶

异或：二者相同为0，不相同为1。

需要的掩码仅在位置n处为1，这样该位置的比特位将会被翻转，而其它所有比特位保持不变。

void toggle(uint8_t *byte, uint8_t n) {
    *byte = *byte ^ (1u << n);
}

read()读取¶

提取单个比特位的值。

步骤：

先将字右移n位
将右移后的字和掩码1，使用位与运算将其它位设置为0

uint8_t read(const uint8_t *byte, uint8_t n) {
    return (*byte & (1u << n));
}

掩码¶

由于编写一长串的0和1及其容易出错，底层开发者完全避开了二进制，改用16进制来编写掩码。