如何判断一个整数是否是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)
}