判断一个整数的二进制第n位是否为1
Table of Contents
这里说的整数都是正整数,负数在计算机中都用补码表示,不能按下文的方法算。
使用二进制表示权限
我们经常用0和1来表示权限的有无,或者选项是否勾选,比如我有以下三个权限,0表示没有这个权限,1表示有这个权限:
查看 | 修改 | 修改 | 十进制 |
---|---|---|---|
0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 2 |
0 | 1 | 1 | 3 |
1 | 0 | 0 | 4 |
1 | 0 | 1 | 5 |
1 | 1 | 0 | 6 |
1 | 1 | 1 | 7 |
三个权限都用0、1来表示,共有7种组合,但我们存储的时候,一般都会把它存储为十进制整数,因为十进制整数比二进制数整容易保存多了(比如111我保存成7即可,如果你存二进制111
,你是存成字符串呢还是把它当十进制数存呢?如果存成字符串,效率不如十进制,如果把它当十进制存,那这个十进制数会超级大,整数类型很可能存不下,就算存的下那也会消耗比较多空间,也没有转化为十进制方便)。
十进制数反推权限方法一
前面我们把权限保存成十进制数字存进数据库了,现在我们要使用它,把它从数据库取出来之后,我怎么知道这个十进制数对应的某一位是0还是1呢?把它转换为二进制,再判断吗?没错,这是一种方法!
以下是用golang实现的十进制转二进制字符串
// DecToBin 用于把十进制数转成2进制,使用的是除2取余法
func DecToBin(n int) string {
result := ""
if n == 0 {
return "0"
}
// 由于n是整数,所以即使n/=2(即n = n/2)是小数,最后赋值给n也只会剩下整数部分,小数部分无论多大(即使是0.9)也会丢失
for ; n > 0; n /= 2 {
lsb := n % 2
// Itoa(Int to ASCII),但事实上就是整数转字符串,Atoi就是数字字符串转数字
result = strconv.Itoa(lsb) + result
}
return result
}
当然其实根本没必要像上边那样转换,因为go的内置函数就可以直接转换
var decimal int64 = 14
# 第一个参数必须是int64类型,所以定义的时候不能用短变量,否则它就不是int64而是int。
# 第二个参数2表示转换为二进制(同理你还可以写成8或16,分别表示转换成8进制和16进制)
binStr := strconv.FormatInt(decimal, 2)
fmt.Println(binStr)
转成二进制字符串后,再用字符串截取方式,获取对应位置的数字(当然它是字符串形式),然后再判断它是字符串0还是1即可知道它有没有这个权限。
但是这种方式并不推荐,因为计算量比较大,也因为有更简单的方法。
十进制数反推权限方法二(推荐)
该方法使用右移>>
+ 按位与&
两个符号来实现。首先要说明一下,我们说二进制的“第n位”都是指从右往左数的第n位。
什么是右移
右移,就是把二进制位向右边移动n位(左侧空出的位置补0,右侧移出的丢弃),注意,我们说的是二进制位,不是二进制数,事实上我们用来做位移的数都是十进制数比较多,毕竟十进制写起来比二进制方便,比如10>>2
,它的意思是把十进制整数10转为二进制数后(事实上根本不用转,因为电脑存数字就是用二进制存的),再把这个二进制数往右移动两位,十进制10转为二进制是1010
:
右移两位之前: 1010
右移两位之后: 1010
右移后实际为: 0010 (左侧空出的两位补0,右侧超出的两位“10”丢弃)
当然你要写二进制一样可以,但是这要看编程语言是否支持,大多数编程语言都用0b
开头表示二进制,比如c、c++、python、php、golang等等,比如0b1010>>2
同样表示十进制10右移两位,只不过写成了二进制形式。
什么是按位与
按位与,就是按二进制位相与,比如6&2
就是十进制的6与十进制的2分别转为二进制后,右对齐,长度不同的话左侧补0,补成长度相同,然后再上下两位对应相与,“与”就是必须两个都为1,结果才是1,否则为0
6: 110
2: 010
---------
值: 010
注意:十进制6与十进制2按位与,直接写成6&2
就行,如果你要写成二进制,那就是0b110&0b10
(大多数编程语言以0b
来表示二进制,javascript ES6支持这种写法,ES6以前是不支持的),但是我们没必要写成二进制,毕竟写起来麻烦,而且写之前你还得转换一下。
反推权限原理
二进制的1只有第一位为1(从右往左数),其它都为0,所以任何数与二进制1按位与,都只有左侧第一位有用,其它全部没用,因为它们与0相与之后都变为0了。
十进制10化为二进制1010
后与二进制的1按位与
10: 1010
1: 0001
----------
结果: 0000
十进制11化为二进制1011
后与二进制的1按位与
11: 1011
1: 0001
----------
结果: 0001
所以,我们要判断一个十进制数的二进制形式第n位是0还是1,只需要把它的第n位向右移动到与二进制1
对齐,然后“按位与”一下,结果为1,说明第n位就是1,结果为0,说明第n位就是0,因为只有1与1相与,结果才会是1。而且任何数与二进制1按位与,最后的结果只有两种,不是0就是1,不会有其它值,无论是十进制还是二进制都一样(因为对于0和1来说,二进制与十进制是一样的)。
反推权限举例
比如,我们想看十进制数11的二进制1011的第3位(二进制第n位都是从右往左数)是0还是1,那么我们可以把这个二进制数往右移动两位,这样它的第三位就刚好跟二进制的1
对齐了
未移动时: 1011
右移两位: 1011
实际数字: 0010 (右移后,左侧空出的位置补0,右侧超出的数字丢弃)
与一相与: 0001 (与二进制1按位相与)
最后结果: 0000 (这个数字转成十进制也是0)
最后结果二进制是0000
,但编程语言中输出都会输出十进制,即0,0就表示没有权限,或者说没有勾选这个选项,反之,1就表示有该权限,或者说勾选了该选项。
编程语言实现
最后用golang写一个函数来实现前面说的理论
func isOne(x int, n int) int {
return (x >> (n - 1)) & 1
}
x >> (n - 1)
表示右移n减1位,因为我们要判断第三位,就要右移两位,这样第三位就会排到第一位与二进制1
对齐,同理,要判断第四位,就要往右移三位,这样第四位才会排到第一位,与二进制1
对齐,所以要n减1。
(x >> (n - 1)) & 1
整句表示x往右移动n减1位之后,再与十进制数1“按位与”,注意&
后面那个1是十进制的1,不是二进制,因为二进制需要以0b
开头,但是这不重要,因为十进制的1转成二进制后,它还是1,这是两个进制数相同的地方。
事实上,可以去掉外部括号变成这样(因为>>
的优先级大于&
)
func isOne(x int, n int) int {
return x >> (n - 1) & 1
}
但是为了避免有些人忘记>>
和&
的优先级,我还是加上了括号,这样一目了然,不需要猜,不需要回想谁的优先级高。
当然我们也可以返回布尔值,这样更方便if条件判断
func isOne(x int, n int) bool {
return (x>>(n-1))&1 == 1
}
