位运算详解

曲镇 · · 2026 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

位运算 Bitwise operation

前言

日常提出疑问,然后引出今天的下文:

  1. 如何在代码里不用 “+” 、“-” 实现加减法的操作?

接下来我就介绍一项一招制敌的技能 —— 位运算

正文

什么是位运算

程序中的所有数在计算机内存中都是以二进制的形式存储的。位运算(Bitwise operation)就是直接对整数在内存中的二进制位进行操作,因此其执行效率非常高。

在程序中使用位运算进行操作,会大大提高程序的性能。

位运算的本质

位运算是在二进制之间操作,粗略地说就是 0 和 1 之间的转换

位运算的基本操作

与运算 &

两个位都是 1 时,结果才为 1

1 & 1 = 1
1 & 0 = 0
100 & 001 = 0
100 & 101 = 100

或运算 |

两个位都是 0 时,结果才为 0,否则为 1

// 二进制
1 | 0 = 1
100 | 001 = 101

异或运算^

又称不进位加法,两个位相同则为 0,不同则为 1

// 二进制
1 ^ 1 = 0
1 ^ 0 = 1
100 ^ 001 = 101
101 ^ 001 = 100     // 如果这里是加法的话,末尾 1 + 1 应该等于 0, 并向前进 1
                    // 异或运算中,这里只等于 0 , 未向前进 1, 所以叫不进位加法

取反运算 ~

又称非操作,0 则变为 1,1 则变为 0(在 golang里, 可以用 ^1进行取反操作)

// 二进制
~1 = 0
~0 = 1

左移运算 <<

向左进行移位操作,高位丢弃,低位补 0; 左移 1 位相当于乘 2, 左移 n 位相当于乘 2 的 n 次方

左移通常用作乘法操作

// 二进制
101 << 1 = 1010
101 << 2 = 10100

// 整型
3 << 1 = 6
3 << 2 = 12

右移运算 >>

向右进行移位操作,对无符号数,高位补 0,对于有符号数,高位补符号位;右移 1 位相当于除 2, 右移 n 位相当于除 2 的 n 次方

右移通常用作除法操作

// 二进制
1000 >> 1 = 100
1000 >> 2 = 10

// 整型
8 >> 1 = 4
8 >> 2 = 2

实战位运算要点

下面介绍几个常用的方法

判断奇偶

奇:(x&1) == 1; 偶: (x&1) == 0

def and_example(x):
    if x & 1 == 0:
        print("偶数")
    if x & 1 == 1:
        print("奇数")

除二

x >> 1

def average(m, n):
    return (m + n) >> 1

清零最低位的 1

x=x&(x-1)

// 二进制
x = 1010
x&(x-1) = 1000

得到最低位的 1

x&-x

// 二进制
x = 1010
-x = 0110 // 这里可以了解一下二进制中负数表示方法
x&-x = 0010

归零

x &~x

// 二进制
x = 1010
x&~x = 0000

解答开篇问题

1. 位操作实现加法

  1. 二进制加法中,可以使用 ^ 进行不进位加法运算
  2. 如果需要的话,将计算的数向前进 1

整体流程如上图,请参照下面代码加以思考:

def add(m, n): # m + n
    if m & n == 0: return n | m     # return 非 0 的数
    return add(m ^ n, (m & n)<< 1)  # m & n 来确定相加的 1 的位置

2. 位操作实现减法

  1. 二进制加法中,可以使用 ^ 进行减法
  2. 如果需要的话,将计算的数向前面数借 1
二进制减法示意图.jpg

整体流程如上图,请参照下面代码加以思考:

def sub(m, n): # m - n
    if n == 0: return m
    return sub(m ^ n, (~m & n) << 1) # (~m & n) << 1 来找到借的 1 的位置

最后

文中如有表述不清之处,请在下面留言,我会第一时间进行完善。

编者希望能给大家带来更多优质的文章;上述内容你觉得还可以的话,请帮我点个赞,谢谢!


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:曲镇

查看原文:位运算详解

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

2026 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传