算法记录

如何判断一个整数是否是2的整数次幂

func modOf(x: Int) -> Bool {
  return false
}

如果一个整数是2的整数次幂，那么，一定其所拥有的bit，一定只有一位是1，其余为0，那么，就可以对其减1，然后与操作，判断结构是否为0，为0 就是整数次幂，否则不是：

func modOf(x: Int) -> Bool {
  return x & (x - 1) == 0
}

如何对2的n次方求模

func modOf(x: Int, n: Int) -> Int {
        return 0
}

先从十进制入手，假设一个数能够被10整除，那么个位一定为0，例如210，120反之，一定无法被10整除例如101、308且个位上的数，就是除之后的模。那么对于除数是100的话，类似，个位与十位都为0，就可以被100整除，个位和十位的数字就是模，例如，123 % 100 = 23。
那么二进制也类似，对于能整除pow(2,n)的数，其末尾的n个bit一定为0，例如n = 2 时，100，1100，1000，11100，一定能被4整除，那么末尾n个bit的值就是模的值，所以modOf方法如下：

func modOf(x: Int, n: Int) -> Int {
  return x & (pow(2,n) - 1)
}

对整数取反的结果

对于无符号整数来说，取反的结果与原始值之和，其实就是Int.Max：

let x: UInt8 = 10
let t: UInt8 = ~x // UInt8.Max - x

对于有符号的整形来说，对于正数取反，其结果就是:

let x: Int8 = 10
let t: Int8 = ~x // -1 * pow(2, n-1) + pow(2, n-1) - 1 - value == -1-value

对于负数来说:

let x: Int8 = -10
let t: Int8 = ~x
// 等价于
let min = Int8(bitPattern: UInt8(pow(2.0,7.0)))
min &- 1 &- (min &+ x) 
-1 - x

计算机中的数据对齐是如何实现的

数据对齐有很多的好处，CPU可以更快的获得数据、缓存友好等，我们以8字节对齐为例，假设，当前数据的偏移量为offset，那么如何对齐数据？

func align(offset: Int) -> Int {
  return 0
}

对齐就是在大于当前的offset之后寻找align的整数倍，如果是十进制的数的话，我们一般这么做（假设align为10）：

(x + 10 -1 ) / 10

但是对于计算机来说，对齐往往都是2的n次幂，所以可以用类似于对2的n次幂求模的方式，求模是取后面的，但是前面的位，就可以用来作为整除的部分，一定能够被2的n次幂整除，

func align(offset: Int, power: Int) -> Int {
  let x = offset + power -1  // 此处的操作是因为，如果offset == power的时候，需要-1
  return x & ~(power - 1)
}