您现在的位置是:首页 > 编程

Go中位运算以及应用场景介绍

编程作者:chenli日期:2022-06-07 10:42:25点击:53

位运算

基本语法

[ 左移 ] << 较常用

1 << 2 //输出十进制4  
二进制位移从0001 移动到 0100  
相比右移更常见,移位后空缺的部分全部填0

[ 右移 ] >>

10 >> 2 //输出十进制 2
二进制位移从1010 移动到 0010  

[ 异或 ] x ^ y //用途:取补集

10 ^ 2 == 8
操作的结果是如果某位不同则该位为1, 否则该位为0

[ 或 ] x | y //用途:取并集

10 | 2 == 10
两个相应的二进位中只要有一个为1, 该位的结果值为1

[ 与 ] x & y //用途:判断x集合是否包含y集 是则返回b 否则返回0

10 & 2 == 2 
两个相应的二进位都为1, 该位的结果值才为1,否则为0

[ 取反 ] ^x

^2 == -3
源码先取反码+1得补码 [补码](https://zhuanlan.zhihu.com/p/99082236)

常量批量位移

package main

import "fmt"

const (
    a = 1 << iota
    b
    c
    d
)

func main() {
    fmt.Printf("%b\n", a)
    fmt.Printf("%b\n", b)
    fmt.Printf("%b\n", c)
    fmt.Printf("%b\n", d)

}

\\1
\\10
\\100
\\1000

或 或异 与 演示

package main

import "fmt"

const (
    a = 11
    b = 123
    c = 342
    d = 421
)

func main() {
    f := a | b | c | d   
    fmt.Println(f & d)  //返回d
    f = f ^ d
    fmt.Println(f & d)  //返回0
}

位运算应用:权限控制

图片alt

package main

import "fmt"
const (
    read = 1 << 0
    write = 1 << 1
    execute = 1 << 2
)
var permission = read | write
func main() {
    fmt.Println(permission & write)   //true
    fmt.Println(permission & execute) //false
}

位运算应用:位图存储(适合存储bool和int)

一、概述

本文将讲述Bit-Map算法的相关原理,Bit-Map算法的一些利用场景,例如BitMap解决海量数据寻找重复、判断个别元素是否在海量数据当中等问题.最后说说BitMap的特点已经在各个场景的使用性。

二、Bit-Map算法

先看看这样的一个场景:给一台普通PC,2G内存,要求处理一个包含40亿个不重复并且没有排过序的无符号的int整数,给出一个整数,问如果快速地判断这个整数是否在文件40亿个数据当中?

问题思考:

40亿个int占(40亿*4个字节)/1024/1024/1024 大概为14.9G左右,很明显内存只有2G,放不下,因此不可能将这40亿数据放到内存中计算。

要快速的解决这个问题最好的方案就是将数据搁内存了,所以现在的问题就在如何在2G内存空间以内存储着40亿整数。

一个int整数在golang中是占4个字节的即要32bit位,如果能够用一个bit位来标识一个int整数那么存储空间将大大减少,算一下40亿个int需要的内存空间为(40亿*4个字节)/32/1024/1024/1024 大概为465 mb,这样的话我们完全可以将这40亿个int数放到内存中进行处理。

具体思路:

1个int占4字节即4*8=32位,那么我们只需要申请一个int数组长度为 int tmp[1+N/32]即可存储完这些数据,其中N代表要进行查找的总数,tmp中的每个元素在内存在占32位可以对应表示十进制数0~31,所以可得到BitMap表:

tmp[0]:可表示0~31

tmp[1]:可表示32~63

tmp[2]可表示64~95

如何判断int数字在tmp数组的哪个下标?

这个其实可以通过直接除以32取整数部分,例如:整数8除以32取整等于0,那么8就在tmp[0]上。另外,我们如何知道了8在tmp[0]中的32个位中的哪个位,这种情况直接mod上32就ok,又如整数8,在tmp[0]中的第8 mod上32等于8,那么整数8就在tmp[0]中的第八个bit位(从右边数起)。

图片alt

go简单实现:

package main

import "fmt"

func main() {
    m := NewBmap()
    m.Add(1)
    fmt.Println(m.Has(21))
}

type Bitmap struct {
    partition []uint64 //分区
    length    int      //已存放个数
}

func NewBmap() *Bitmap {
    return &Bitmap{}
}

func (bitmap *Bitmap) Has(num int) bool {
    word, bit := num/64, uint(num%64)
    return word < len(bitmap.partition) && (bitmap.partition[word]&(1<<bit)) != 0
}

func (bitmap *Bitmap) Add(num int) {
    partition := num / 64 //取整除后得到分区号
    bit := uint(num % 64) //取余,得到分区位置

    for partition >= len(bitmap.partition) {
        //分区号超出现有分区,则新开分区
        bitmap.partition = append(bitmap.partition, 0)
    }

    if bitmap.partition[partition]&(1<<bit) == 0 {
        // 判断分区中没有则添加
        bitmap.partition[partition] |= 1 << bit
        bitmap.length++
    }
}

func (bitmap *Bitmap) Len() int {
    return bitmap.length
}

位运算应用:布隆过滤器

文章评论