算法通关村——位运算

news/2024/12/13 16:06:39/

1. 常见的位运算

1.1 与 &

&:两个数对应的位都是1,那么结果才是1
1 & 1 = 1
1 & 0 = 0;
0 & 0 = 0;

1.2 或 |

|: 只要两个数对应的位有一个1,结果就是1
1 | 1 = 1;
1 | 0 = 1;
0 | 0 = 0;

1.3 异或^

^: 只有两个数的位都一样的时候才是返回0,否则返回1
1 ^ 1 = 0
0 ^ 1 = 1
0 ^ 0 = 0;

1.4 取反 ~

~: 就是取反,如果位是1,取反就是0
~1=0
~0=1

2. 移位运算

左移:<< 全部二进制左移若干位(如果左移一位,就是除以2)
右移:>> 全部二进制右移若干位

3. 位1的个数

位1的个数
编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。

3.1 右移

只需要将每一位和1进行与&操作,如果当前位是1,那么就计数
i=0 00000000000000000000000000001011 & …1=1
i=1 00000000000000000000000000000101 & …1=1
i=2 00000000000000000000000000000010 & …1=0
i=3 00000000000000000000000000000001 & …1=1

结果是3

 public int hammingWeight(int n) {int count =0;for(int i=0;i<32;i++){count+=(n>>i)&1;}return count;}

3.2 左移

先设置一个mask之用于左移比较是否位相同
00000000000000000000000000001011 & 1 =0
00000000000000000000000000001011 & 01 = 0
00000000000000000000000000001011 & 001 =0

00000000000000000000000000001011 & 00000000000000000000000000001 = 1
00000000000000000000000000001011 & 000000000000000000000000000001 = 0
00000000000000000000000000001011 & 0000000000000000000000000000001 = 1
00000000000000000000000000001011 & 00000000000000000000000000000001 = 1

 public int hammingWeight(int n) {int count =0;int mask = 1;for(int i=0;i<32;i++){if((n & mask) !=0){count++;}mask<<=1;}return count;}

3.3 n&(n-1)

将二进制最后一个1变成0,直到n最后变成0
00000000000000000000000000001011 & 00000000000000000000000000001010 = 00000000000000000000000000001010
count = 1;

00000000000000000000000000001010 & 00000000000000000000000000001001 = 00000000000000000000000000001000
count = 2;

00000000000000000000000000001000 & 00000000000000000000000000000111 =
0000000000000000000000000000000
count =3;

 public int hammingWeight(int n) {int count =0;while(n!=0){n=n&(n-1);count++;}return count;}

这种效率也是比较高的,经常使用,前两个位移都是需要遍历32次,而n&(n-1)只需要n为0的时候就退出
在这里插入图片描述

4. 比特位计数

比特位计数
给你一个整数 n ,对于 0 <= i <= n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n + 1 的数组 ans 作为答案。
输入:n = 2
输出:[0,1,1]
解释:
0 --> 0
1 --> 1
2 --> 10

4.1 右移

这里面的的计算1的个数就可以采用之前的( n>>i ) &1,其中n是当前的值,而i是右移的位数
很显然,因为元素大小是在0-n这个范围内,所以是按照相应下标就可以知道当前的值,那么再次&1比较,然后右移,就可以算出1的个数,然后赋值给数组。

    public int[] countBits(int n) {int [] res = new int [n+1];for(int i=0;i<=n;i++){for(int j=0;j<32;j++){res[i] += (i >>j)&1;}}return res;}

此方法缺点在于时间耗费比较长,因为每个元素都要遍历右移32次,才能计算1的个数

4.2 位的性质 n&(n-1)

public int[] countBits(int n) {int count =0;int [] res = new int [n+1];for(int i=0;i<=n;i++){res[i] = getOneCount(i);}return res;}public int getOneCount(int x){int count =0;while(x!=0){x=x&(x-1);count++;}return count;}

5. 颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。提示:请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
在 Java 中,编译器使用二进制补码记法来表示有符号整数。因此,在 示例 2 中,输入表示有符号整数 -3,输出表示有符号整数 -1073741825

5.1 逐位颠倒

一开始想的是直接反转这个二进制数,直接使用Integer的reverse是肯定不行的。
首先先获取到n的最后一位,然后n进行逻辑右移,和reversed反转数进行相加,直到n变成0
00000010100101000001111010011100右移31位,最低位是0
n逻辑右移1位
00000001010010100000111101001110右移30位,最低位是0

 public int reverseBits(int n) {int reversed =0;int length = 31;while(n!=0){reversed += (n&1)<<length;// 逻辑右移n >>>= 1;length--;}return reversed;}

6. 两整数之和

两整数之和
给你两个整数 a 和 b ,不使用 运算符 + 和 - ​​​​​​​,计算并返回两整数之和。
输入:a = 2, b = 3
输出:5

6.1 异或+与

2:010
3:011
5:101
可以看出相同为0,不同为1,这是异或,对于不需要进位的部分采用a^b , 但是需要关注首位是0还是1,进位部分就要采用a&b,只有两个都是1的时候才需要进位。

public int getSum(int a, int b) {while(b!=0){int sign = (a & b) << 1;a = a ^ b;b = sign;}return a;}

a&b= 010 010 << 1 = 100 sign = 100
a^b= 001 a = 001
b = 100

a&b = 100 & 001 = 000 000<1 =000 sign =0
a^b = 100 ^ 001 = 101 a = 101
b =0
退出

a=101 =5

7. 递归乘法

递归乘法
递归乘法。 写一个递归函数,不使用 * 运算符, 实现两个正整数的相乘。可以使用加号、减号、位移,但要吝啬一些。
输入:A = 3, B = 4
输出:12

7.1 位运算

例如3 * 4,就是3 * 2 ^ 2,也就是3<<2,左移两位
例如1 * 10,就是1 (2+8)就是1 * 2^1+12 ^3 就是1 <<1 +1<<3

先找出两者之间的最小值和最大值,选取最小值作为乘数的原因是次数较少,然后判断min的最右一位是不是1,是1就添加该位到结果中,然后最小值右移一位

 public int multiply(int A, int B) {int add = 0;int min = Math.min(A,B);int max = Math.max(A,B);for(int i=0;min!=0;i++){if((min & 1) == 1){add  += max<< i;}min >>= 1;}return add;}

例如 1 * 10 min = 1,max = 10, min &1 =1, add = 10 << 0 = 1010=10
min >>1 = 0 退出

例如 3* 4 min = 3 max =4 min & 1= 1 add = 4 << 0 =4
min >> 1 = 01 min & 1= 1 add = 4 + 4 << 1 = 4 + 8 = 12


http://www.ppmy.cn/news/1046819.html

相关文章

c语言实现MD5算法

MD5加密 文章目录 MD5加密MD5介绍应用场景代码分析 &#xff08;基于qt5.14.2&#xff09;测试记录 MD5介绍 1。 一种单向加密算法&#xff0c;即对明文加密&#xff0c;而不能通过密文得到明文。对原数据的任何改动&#xff0c;哪怕是1字节&#xff0c;得到的MD5值都有很大的区…

漏洞指北-VluFocus靶场专栏-工具篇

漏洞指北-VluFocus靶场专栏-番外篇奇技淫巧 &#x1f338;1、burp suite 、中国蚁剑工具、Strut2扫描软件地址&#x1f338;&#x1f338;2、burp suite使用&#x1f338;step1 浏览器开启代理&#xff0c;**推荐使用&#xff1a;SwitchyOmega** step2 确认浏览器端口和burp su…

Linux 线程同步——信号量

一、线程同步的概念 这里的同步就是对程序的执行进行控制&#xff0c;因为如果不进行控制就会出现错误的问题&#xff0c;这里的控制是为了保证程序的正确性。 线程同步指的是当一个线程在对某个临界资源进行操作时&#xff0c;其他线程都不可以对这个资源进行操作&#xff0…

什么是原型(prototype)和原型链(prototype chain)?如何继承一个对象的属性和方法?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 原型&#xff08;Prototype&#xff09;和原型链&#xff08;Prototype Chain&#xff09;⭐ 原型&#xff08;Prototype&#xff09;⭐ 原型链&#xff08;Prototype Chain&#xff09;⭐ 继承属性和方法⭐ 写在最后 ⭐ 专栏简介 前端入…

shell脚本文本 三剑客AWK

TOC 一.AWK工具介绍 AWK是一种处理文本文件的语言&#xff0c;是一个强大的文本分析工具可以在无交互的模式下实现复杂的文本操作相较于sed常作用于一整行的处理&#xff0c;awk则比较倾向于一行当中分成数个字段来处理&#xff0c;因为awk相当适合小型的文本数据 1.1AWK命令…

macOS(m1/m2)破解Sublime Text和Navicat16

破解Sublime Text 说明&#xff1a;全程使用的是终端操作 1. 下载Sublime Text&#xff0c;建议使用brew下载 2. 进入到下载的app的文件夹 cd "/Applications/Sublime Text.app/Contents/MacOS/"3. 执行以下操作以确认版本是否匹配 md5 -q sublime_text | grep -i…

RPM包的概念以及制作过程

RPM包的概念以及制作过程 1. 软件包管理工具的背景介绍2. RPM&#xff08;Red-Hat Package Manager&#xff09;2.1 rpm包的命名规范2.2 rpm的基础命令2.3 安装与卸载 3. RPM包的制作3.1 源码包的制作3.2 .spec配置文件的构建3.3 rpmbuild命令编译验证 4. 软件仓库制作4.1 安装…

【rust/egui】(四)看看template的app.rs:update以及组件TopBottomPanelButton

说在前面 rust新手&#xff0c;egui没啥找到啥教程&#xff0c;这里自己记录下学习过程环境&#xff1a;windows11 22H2rust版本&#xff1a;rustc 1.71.1egui版本&#xff1a;0.22.0eframe版本&#xff1a;0.22.0上一篇&#xff1a;这里 update update实际上还是eframe::App的…