判断一个整数的二进制第n位是否为1

判断一个整数的二进制第n位是否为1

这里说的整数都是正整数,负数在计算机中都用补码表示,不能按下文的方法算。

使用二进制表示权限

我们经常用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
}

十进制数反推权限方法三(推荐)

假设我有ABCD四个选项,我勾选了ACD,B没有勾,按顺序排列,勾了用1表示,没有勾用0表示,如下所示

A B C D
1 0 1 1

按这个定义,我们可以转换出一组选项与数字的对应关系(就类似Linux系统的权限)

A => 1000
B => 0100
C => 0010
D => 0001

以上对应关系,我们一般是在代码中用一个文件列出这个对应关系,但是如果8直接写成1000,会被认为是十进制数1000,一般加个0b开头,编程语言就会认为它是二进制了(当然也可以用0x开头,这样就是16进制,16进制能表示的数更多,但我这里为了简单举例,所以使用二进制),所以我们要写成

A => 0b1000
B => 0b0100
C => 0b0010
D => 0b0001

假设我选了ACD,那么这三个数是1000+0010+0001=8+2+1=11,但实际用代码计算的时候,我们只需要把它们“按位或”即可,如下所示,最终得出1011,转成十进制就是11

1000 | 0010 | 0001 = 11

# 计算如下
1000
0010
0001
----
1011

然后我把1011转成十进制,也就是11,存到数据库,如果我想知道B选项有没有被勾选,我只需要取出这个11,然后从代码中找到B => 0b0100,然后把两个数做“按位与”操作11&0b0100

1011
0100
----
0000

可以发现,11 & 0b0100 = 0,所以没有选中的选项,与我们的“和”做“按位与”操作,它的结果是0。

我们再来验证一下其它的,比如我想知道ACD有没有被选中

11 & 0b1000 = 8 =>(0b1000转十进制为8)
11 & 0b0010 = 2 =>(0b0010转十进制为2)
11 & 0b0001 = 1 =>(0b0001转十进制为1)

可以发现,有被选中的选项与我们的结果做“按位与”运算后,它的结果是等于该选项本身。


基于以上原理,我们来写一段实际可以运行的代码(以下代码使用golang编写)

package main

import "fmt"

const (
    A int = 0b1000
    B int = 0b0100
    C int = 0b0010
    D int = 0b0001
)

// calcFlag 用于计算并返回多个选项按位或的结果
func calcFlags(flags []int) int {
    sum := 0
    for _, v := range flags {
        // 把所有选项做“按位或”操作
        sum = sum | v
    }
    return sum
}

// addFlag 用于添加一个flag
func addFlag(x int, flag int) int {
    return x | flag
}

// delFlag 用于从x中删除某个flag,比如(A|B)&(^B)=A
// ^flag 表示按位取反(golang中按位取反与异或操作符共用一个)
func delFlag(x int, flag int) int {
    return x & (^flag)
}

// checkFlag 用于检测某个选项是否被选中
func checkFlag(x int, flag int) bool {
    return x&flag == flag
}

func main() {
    // 假设我选了ACD
    options := []int{A, C}
    // 计算ACD做“按位与”运算后的和
    sum := calcFlags(options)
    // 添加D
    sum = addFlag(sum, D)
    // 删除C
    sum = delFlag(sum, C)
    // 这个数字用于存储到数据库
    fmt.Println("sum:", sum)

    // 当从数据库取出sum后,就可以用它来判断ABCD哪个选项哪个选了,哪个没选
    isAChecked := checkFlag(sum, A)
    isBChecked := checkFlag(sum, B)
    isCChecked := checkFlag(sum, C)
    isDChecked := checkFlag(sum, D)
    fmt.Println("A:", isAChecked, "\nB:", isBChecked, "\nC:", isCChecked, "\nD:", isDChecked)

    // === 打印结果 ===
    // sum: 9
    // A: true
    // B: false
    // C: false
    // D: true

    // 我们先添加了AC,后添加了D,然后删除了C,所以剩下AD选中,而BC未选,输出结果确实是BC为false,符合我们前面的理论!
}

十进制数反推权限方法四(推荐)

什么是掩码

一个二进制数第n位的掩码就是“掩盖”掉除该位之外的所有位。比如1011第三位(从右往左数)的掩码是0100

原二进制码:1011
第三位掩码:0100

可以看到,第三位的掩码就是用0去“掩盖”除了第三位之外的所有位。

那怎样才能计算得到一个二进制第n位的掩码呢?很简单,只需要把1左移n-1位就行(n-1是因为要从0开始数,并且要注意,第n位都是指从右往左数第n位)。

我们来试一下,1011,从右往左数第3位为0,但计算中要从0开始数,所以第三位的下标就是2,我们把1左移2位1<<2

未左移前:0001
左移两位:0100 (空出的位置补0)

所以,要得到一个二进制数第n位的掩码,只需要把1左移n-1位即可。

同理,1011第二位的掩码就是1左移2-1位,即1左移1位,也就是0010。

使用掩码获取对应位

前面我们计算出1011第三位的掩码是0100,我们把这两个数做“按位与”运算

1011
0100
----
0000

1011&0100 = 0

我们再试试1011第二位的掩码“0010”与“1011”按位与

1011
0010
----
0010

由以上的计算可总结出,原码与它的第n位掩码做按位与运算,如果第n位是0,那么结果就是0,如果第n位是1,那么结果就是第n位本身(或者换一种说法,叫“不为零”)。

十进制数反推权限方法三(推荐)中所说,我们把ABCD四个选项用四个码表示

A B C D
1 0 1 1
A => 1000
B => 0100
C => 0010
D => 0001

写成代码(我这里使用golang)如下所示

func isOne(x int, n int) bool {
    return x&(1<<(n-1)) != 0
}
打赏
订阅评论
提醒
guest

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

0 评论
内联反馈
查看所有评论
0
希望看到您的想法,请您发表评论x
()
x

扫码在手机查看
iPhone请用自带相机扫
安卓用UC/QQ浏览器扫

判断一个整数的二进制第n位是否为1