位运算符

取反运算

• 位取反运算符(~) 是对所有位的数组进行取反

• 0000 1111 取反操作后变成 1111 0000

  
  取反运算

与运算

• 位的与运算符(&) 可以对两个数的比特位进行合并,它会返回一个新的数,只有当这两个数都是1的时候才能返1

• 1111 1100 & 0011 1111 结果是 0011 1100

  
  与运算

或运算

• 位或运算符(|) 可以对两个比特位进行比较,然后返回一个新的数,只要两个操作位任意一个为1时,那么对应的位数就位1.

• 1010 1100 | 0101 1101 结果是 1111 1101

  
  或运算

异或运算

• 位异或运算符,或者说"互斥或"(^) 可以对两个数的比特位进行比较.他返回一个新的数,当两个操作数的对应位不相同时,该数的对应位就为1

• 0001 0100 ^ 0000 0101 结果是 0001 0001

  
  异或运算

位左移和右移运算

• 位左移运算符(<<)和位右移运算符(>>) 可以把所有位的数字向左或者向右移动一个确定的位数
• 位左移和右移具有给证书乘以或者除以2的效果. 将一个数左移一位相当于把这个数乘2,讲一个数右移一位相当于把这个数除以2

无符号整数的位移操作

• 已经存在的比特位按指定的位数进行左移和右移
• 任何移动超出整型存储边界的位都会被丢弃

• 用0来填充向左或向右移动后产生的空白位

  
  无符号整数的位移操作

有符号整数的位移操作

• 有符号整数使用他的第一位(所谓的符号位)来表示这个整数是正数还是负数.符号位是0表示正数,1表示负数.
• 其余的位数(所谓的数值位)存储了实际的值.有符号正整数和无符号的存储方式是一样的,都是从0开始算起.

• 但是负数的存储方式略有不同,他存储的是2的n次方减去他的绝对值,这里的n为数值为的位数

  
  有符号整数的位移操作

补码表示的优点

• 首先,如果像个-4加个-1,只需要将两个数的全部8个比特位想加(包括符号位),并且将计算结果中超出的部分丢弃.

  
  补码

• 其次，使用二进制补码可以使负数的位左移和右移操作得到跟正数同样的效果，即每向左移一位就將自身的数值乘以2，每向右移一位就将自身的数值除以2。要达到此目的，对有符号整数的右移有一个额外的规则：当对正整数进行位右移操作时，遵循与无符号整数相同的规则，但是对于移位产生的空白位使用符号位进行填充，而不是0。

  
  补码

位运算符经典算法

1.题目:不借助临时变量,交换两个变量的值.

    var a = 10 // 0000 1010
    var b = 8  // 0000 0100
    a = a ^ b  // a = 0000 1010 ^ 0000 0100 = 0000 1110
    b = a ^ b  // b = 0000 1110 ^ 0000 0100 = 0000 1010
    a = a ^ b  // a = 0000 1110 ^ 0000 1010 = 0000 0100
    print(a) // 打印: 8
    print(b) // 打印: 10

2.题目:给定一个无符号证书(UInt)变量,求其二进制表示中"1"的个数,要求算法的执行效率尽可能高

思路1
看一个8位整数1010 0001,先判断最后一位是否为1,而&操作可以达到目的.可以把这个8位的数与0000 0001进行&操作.如果结果为1,则表示当前8位数的最后一位是1,否则是0. 怎么判断第二位呢?向右移位(>>),再延续前面的判断即可.

func getCount(num: UInt) -> UInt {
    // 记录"1"的个数
    var count: UInt = 0
    // 转成变量
    var temp = num
    while temp != 0 {
        count += temp & 1
        temp = temp >> 1
    }
    return count
}
print(getCount(num: 0x10010101)) // 打印: 4

思路2
为了简化这个问题,我们只考虑高位有1的情况.例:1100 000,如何跳过低位的6个0,而直接判断第七位的1呢?我们可以设计1100 0000 和1011 0000 (也就是1100 0000 - 1)做&操作,消去低位的1.如果得到的结果为0,说明我们已经找到或者消去里面最后一个1.如果不为0,那么说明我们消去了最低位的1,但二进制中还有其他的1,我们的计数器需要加1,然后继续上面的操作.

操作步骤
计数器 count = 0
步骤一: 整数不为0,说明二进制里面肯定有1,count = 1
1100 0000 & 10011 1111(10011 1111 = 1100 0000 - 1) = 1000 0000 消去第七位的1
步骤二: 结果不为0,说明二进制里还有1,count = 2
1000 0000 & 0111 1111(0111 1111 = 1000 0000 - 1) = 0 消去第八位的1
步骤三: 结果为0,终止,返回count = 2

func getCount2(num: UInt) -> Int {
    var temp = num
    var count = 0
    
    while temp != 0 {
        count += 1
        temp = temp & (temp - 1)
    }
    return count
}
print(getCount2(num: 0x11010101)) // 打印:5

3.题目: 给定一个无符号整型变量,判断是否为2的整数次幂

思路:一个整数如果是2的整数次方,那么他的二进制表示中有且只有一位是1,其他都是0.根据前面分析,把这个整数减1后再和他自己做&运算,这个整数中唯一的1也就变成了0,也就得到的结果为0.

func isPowerOfTwo(num: UInt) -> Bool {
    return (num & (num - 1)) == 0
}
print(isPowerOfTwo(num: 0x00000011)) // 打印:false
print(isPowerOfTwo(num: 128)) // 打印:true

4.题目: 有很多成对出现的正整数保存在磁盘中,成对的数字不一定是相邻的,如2,3,4,5,4,2,3......,由于意外消失了一个数字,如何尽快找到是哪个数字消失?

思路:N表示任意数,N ^ 0的结果都是N他本身,N ^ N的时候结果是0.把所有的数字做异或运算,其中两两个相同的数字就会低消,剩余的就是那唯一不成对的一个数了

func findNum(nums: Array<Int>) -> Int {
    var result = 0
    for num in nums {
        result = result ^ num
    }
    return result
}
print(findNum(nums: [2,3,2,4,5,4,3])) // 打印:5

5.题目: 在题目4的基础上,如果丢失的是两个数字,并且这两个数字不相同,求找到这两个数字

func findTwoNum(nums: Array<UInt>) -> (UInt, UInt) {
    var lostNum1: UInt = 0
    var lostNum2: UInt = 0
    var temp: UInt = 0
    // 计算两个数的^结果
    for num in nums {
        temp = temp ^ num
    }

    var flag: UInt = 1
    while (temp & flag) == 0 {
        flag = flag << 1
    }
    
    for num in nums {
        if num & flag == 0 {
            lostNum1 = lostNum1 ^ num
        }else {
            lostNum2 = lostNum2 ^ num
        }
    }
    return (lostNum1, lostNum2)
}
print(findTwoNum(nums: [2,3,2,4,5,4,3,10])) // 打印:(10, 5)