golang[108]-2的幂

单精度浮点数可以表达的范围是:2^-149 - 2^127
Denormalized number 从2^-149 - 2^-127
Normal number 2 ^-126 - 2^127

Power of Two 指数位Exponent 小数位Fraction
-149 0 00000000 00000000000000000000001
-148 0 00000000 00000000000000000000010
-147 0 00000000 00000000000000000000100
-128 0 00000000 01000000000000000000000
-127 0 00000000 10000000000000000000000
-126 0 00000001 00000000000000000000000
-125 0 00000010 00000000000000000000000
-124 0 00000011 00000000000000000000000
-2 0 01111101 00000000000000000000000
-1 0 01111110 00000000000000000000000
0 0 01111111 00000000000000000000000
1 0 10000000 00000000000000000000000
2 0 10000001 00000000000000000000000
3 0 10000010 00000000000000000000000
4 0 10000011 00000000000000000000000
125 0 11111100 00000000000000000000000
126 0 11111101 00000000000000000000000
127 0 11111110 00000000000000000000000

从上表中可以看出,以2为底的单精度指数有以下特点:
1、指数位为0,而小数位只有一个1位
2、指数位介于1到254之间,小数位为0.

Power of Two Exponent Fraction
-1074 0 00000000000 0000000000000000000000000000000000000000000000000001
-1073 0 00000000000 0000000000000000000000000000000000000000000000000010
-1072 0 00000000000 0000000000000000000000000000000000000000000000000100
-1024 0 00000000000 0100000000000000000000000000000000000000000000000000
-1023 0 00000000000 1000000000000000000000000000000000000000000000000000
-1022 0 00000000001 0000000000000000000000000000000000000000000000000000
-1021 0 00000000010 0000000000000000000000000000000000000000000000000000
-1020 0 00000000011 0000000000000000000000000000000000000000000000000000
-2 0 01111111101 0000000000000000000000000000000000000000000000000000
-1 0 01111111110 0000000000000000000000000000000000000000000000000000
0 0 01111111111 0000000000000000000000000000000000000000000000000000
1 0 10000000000 0000000000000000000000000000000000000000000000000000
2 0 10000000001 0000000000000000000000000000000000000000000000000000
3 0 10000000010 0000000000000000000000000000000000000000000000000000
4 0 10000000011 0000000000000000000000000000000000000000000000000000
1021 0 11111111100 0000000000000000000000000000000000000000000000000000
1022 0 11111111101 0000000000000000000000000000000000000000000000000000
1023 0 11111111110 0000000000000000000000000000000000000000000000000000

从上表中可以看出,以2为底的双精度指数有以下特点:
1、指数位为0,而小数位只有一个1位
2、指数位介于1到2046之间,小数位为0.

字节序

指定数字二进制编码内的字节如何在内存中排序。有大端序与小端序之分。
大端序 : 高位高字节
小端序: 高位低字节

2^-2 大端排序为 00111110100000000000000000000000
2^2 小端排序为 00000000000000001000000000111110

判断2的幂的10种方法

以单精度浮点数为例。

方法1

看成是10进制,不断除以2。 2的次方数除到最后为1

1
2
3
4
5
6
func isPowerOfTwo( x uint64) bool {
for x % 2 ==0 && x > 1 {
x /= 2
}
return x == 1
}

方法2

单精度浮点数最多31个数。

1
2
3
4
5
6
7
8
9
10
11
func isPowerOfTwo2( x uint32) bool {
return x == 1 || x == 2 || x == 4 || x == 8 || x == 16 || x == 32 ||
x == 64 || x == 128 || x == 256 || x == 512 || x == 1024 ||
x == 2048 || x == 4096 || x == 8192 || x == 16384 ||
x == 32768 || x == 65536 || x == 131072 || x == 262144 ||
x == 524288 || x == 1048576 || x == 2097152 ||
x == 4194304 || x == 8388608 || x == 16777216 ||
x == 33554432 || x == 67108864 || x == 134217728 ||
x == 268435456 || x == 536870912 || x == 1073741824 ||
x == 2147483648
}

方法3

1
2
3
4
5
6
7
8
// 不断乘以2,逼近参入参数
func isPowerOfTwo3( x uint32) bool {
var powerOfTwo uint32 = 1;
for powerOfTwo < x && powerOfTwo < 2147483648{
powerOfTwo *= 2;
}
return (x == powerOfTwo);
}

方法4

1
2
3
4
5
6
7
8
9
10
11
12
// 事先存好数组,遍历不断逼近参入参数
func isPowerOfTwo4( x uint32) bool {
powerOfTwo := [32]uint32{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,
65536,131072,262144,524288,1048576,2097152,4194304,8388608,
16777216,33554432,67108864,134217728,268435456,536870912,
1073741824,2147483648}
var exponent = 0;
for powerOfTwo[exponent] < x && exponent < 31{
exponent++;
}
return (x == powerOfTwo[exponent])
}

方法5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 二分查找
func isPowerOfTwo5( x uint32) bool {
powerOfTwo := [32]uint32{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,
65536,131072,262144,524288,1048576,2097152,4194304,8388608,
16777216,33554432,67108864,134217728,268435456,536870912,
1073741824,2147483648}
isAPowerOfTwo := false
interval := 16;
exponent := interval;

switch x {
case 0:
isAPowerOfTwo = false
case 1:
isAPowerOfTwo = true
break
default:
for x != powerOfTwo[exponent] && interval>1{
if x < powerOfTwo[exponent]{
exponent -= interval / 2
}else {
exponent += interval / 2
}
interval /= 2
}
isAPowerOfTwo = (x == powerOfTwo[exponent])
}
return isAPowerOfTwo
}

方法6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// math.log函数求出2的幂,与2的次方作对比
func isPowerOfTwo6( x uint32) bool {
powerOfTwo := [32]uint32{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,
65536,131072,262144,524288,1048576,2097152,4194304,8388608,
16777216,33554432,67108864,134217728,268435456,536870912,
1073741824,2147483648}
isAPowerOfTwo := false
if x>0 && x < 2147483648{
exponent := uint32(math.Log2(float64(x)))
isAPowerOfTwo = (x == powerOfTwo[exponent] ||
x == powerOfTwo[exponent+1])
}
return isAPowerOfTwo
}

方法7

1
2
3
4
5
6
7
8
9
10
11
12
// 统计2进制位的个数,2的次方只有1个2进制位
func isPowerOfTwo7( x uint32) bool {
numberOfOneBits := 0

for x > 0 && numberOfOneBits <=1{
if ( x & 1 ) == 1 {
numberOfOneBits++
}
x >>= 1
}
return numberOfOneBits == 1
}

方法8

2的次方第一位是1,其他位为0.

1
2
3
4
5
6
func isPowerOfTwo8( x uint32) bool {
for (x & 1) == 0 && x > 1{
x >>= 1
}
return x == 1
}

方法9

malloc.c in the GNU C Library 中的实现方法。

1
2
3
func isPowerOfTwo9( x uint32) bool {
return (x != 0) && x & (x - 1) == 0
}

下面简单说明一下x & (x - 1) == 0 的原理。
x的二进制从左到右 至少有一个为1的位,标记为i。如果i右边的位都为0,正好是2的次方数。那么 x - 1 在i处为0,在 i右边都为1,这时满足 (x & x - 1) ==0
假设 i右边至少有一位不为0, 那么 x - 1 在i 位仍然为 1 ,这时不满足 (x & x -1) == 0
得证。

方法10

1
2
3
func isPowerOfTwo10( x uint32) bool {
return ((x != 0) && ((x & (^x + 1)) == x))
}

证明方法和方法9相似。

10的正次方数与2进制之间的有趣性质

从下表中我们能够发现,10的正次方数转换为2的次方数后,末尾都是相同的。
原因在于 10^n = 2^n * 5^n 5的次方数总是以1结尾的。 而2^n 相当于左移n位

Power of Ten (in Decimal) Power of Ten (in Binary)
1 1
10 10 10
100 1100 100
1000 111110 1000
10000 100111000 10000
100000 11000011010 100000

因此10^n - 1 有如下性质:

n 10n-1 (in decimal) 10n-1 (in binary)
1 9 1001
2 99 1100011
3 999 1111100111
4 9999 10011100001111
5 99999 11000011010011111
6 999999 11110100001000111111
7 9999999 100110001001011001111111
8 99999999 101111101011110000011111111
9 999999999 111011100110101100100111111111
10 9999999999 1001010100000010111110001111111111
11 99999999999 1011101001000011101101110011111111111
12 999999999999 1110100011010100101001010000111111111111

在google中做计算

Expression Result Notes
2^32 4 294 967 296 Positive power of two
2^-6 0.015625 Negative power of two
1/2^6 0.015625 Negative power of two
(22)3 64 Composed power of two
8^7 2 097 152 Power of eight
716^2 + 1316 + 9 2 009 Convert 0x7D9 to decimal by hand
lg(256)/lg(16) 2 Change of base computes log16(256) = 2
15/2^6 0.234375 Dyadic fraction
lg(65536) 16 log2(216) = 16
log(2^32) 9.63295986 232 is 10 digits long in base 10

10进制转2进制

Expression Result
2009 to binary 0b11111011001
0x07D9 to binary 0b11111011001
0o3731 to binary 0b11111011001

10进制转16净值

Expression Result
2009 to hex 0x7D9
0b11111011001 to hex 0x7D9
0o3731 to hex 0x7D9

10进制转16进制

Expression Result
2009 to octal 0o3731
0b11111011001 to octal 0o3731
0x07D9 to octal 0o3731

转10进制

Expression Result
0b11111011001 to decimal 2009
0x07D9 to decimal 2009
0o3731 to decimal 2009

计算加进制转换

Expression Result
0b1010 + 0b1011 to decimal 21
0xA * 0xF to binary 0b10010110
0o24 / 0o12 to hex 0x2
2^10 + 2^8 + 2^1 to binary 0b10100000010