代码编织梦想


文章最后编辑时间:2020-08-30 17:35

位运算

  现代计算机中,几乎都是二进制计算机(三进制计算机仅有少量),所有的数据都以二进制的形式存储在设备中。
  位运算就是直接对整数在内存中的二进制位进行操作。

常见的位运算

  需要注意,位运算是针对 二进制 的运算,对每一个位进行布尔运算操作。所以 手动 进行 位运算计算 时,需要将数转换成二进制的表示形式,再进行计算。

1 按位与

  只有对应位上两个都为1时,结果才得1,只要有一个为0,结果就是0,类似乘的关系。
在这里插入图片描述

2 按位或

对应位上有一个为1,结果就为1。两个都为0,结果才得0,类似加的关系。
在这里插入图片描述

3 按位取反

对每一位进行取反操作,如果是1则结果为0,是0则结果为1.
在这里插入图片描述

4 按位异或

当两个对应位不同时结果才为1,相同时得0.
在这里插入图片描述

5 按位同或

当两个对应位相同时结果才为1,不同时得0.
在这里插入图片描述

6 左移

将二进制位上的数向左移动,右边补0.
在这里插入图片描述

7 带符号右移

有符号整数最高位代表着数的正负,负数最高位为1。带符号右移是右移时,左边补充最高位上的值。负数右移,左边补1.
在这里插入图片描述

8 无符号右移

二进制上的数向右移动,右移时左边补0。

在这里插入图片描述

编程语言中的位运算

  位运算主要有以下几种:

位运算C语言操作Java操作
按位与a & ba & b
按位或a | ba | b
按位异或a ^ ba ^ b
按位取反~a~a
左移a << ba << b
带符号右移a >> ba >> b
无符号右移a >>> b

嵌入式常用的位运算操作

BIT_N 表示 代表对应位的数,即 (1 << N)。

位的二进制形式输出

  在C语言中,printf并不能直接以二进制的形式输出数,为了可以方便查看二进制位的值,编写如下函数,可以将某一个数转成不同进制的表示形式并输出。

任意进制的输出(2~36进制)

void printBase(unsigned int num, int nBit, int base)
{
	char a[33] = "";
	int n;
	for (n = 0; num; num /= base) {
		a[n++] = num % base;
	}
	
	for (int i = nBit - 1; i >= 0; i--) {
		if (i >= n)
			putchar('0');
		else
		(a[i] < 10) ? putchar(a[i] + '0') : putchar(a[i] + 'a' - 10);
		
		if (i % 4 == 0)
			putchar(' ');
	}
}

二进制形式的输出

void printBin(unsigned int num, int nBit)
{
	printBase(num, nBit, 2);
}

位置位

置位即将某一二进制位置为1

a = a | BIT_N;
简写为
a |= BIT_N;

对多位同时置为,可以将多个BIT_N位或

a |= (BIT_N1 | BIT_N2 | BIT_N3);

位清零

  对某一位清零, 使用位与运算,对应位与0相与得0, 其它位与1相与不变。
  对应位为0的码,使用BIT_N取反即可

a = a & (~BIT_N);

简写为

a &= ~BIT_N;

对多位同时清零,可以将多个BIT_N位或。

a &= ~(BIT_N1 | BIT_N2 | BIT_N3);

取a为1,b为0的位

  a ⋅ b ˉ \ a \cdot \bar b  abˉ, 如果取a为0, b 为1的位,交换a和b的位置即可。

c = a & (~b);

或者

c = (a ^ b) & a;

位逆序

常规逆序

  • 新数左移,原数移出的位放入新数最低位,原数右移
  • 复杂度为   N \ N  N
long long bitReverse(unsigned int num, int N = 64)
{
	unsigned int ans = 0;
	while (N--) {
		ans <<= 1;
		ans |= ans & 1;
		num >>= 1;
	}
	return ans;
}

蝴蝶算法

  • 将一个二进制数上的N位逆序, 每次左右分半,进行交换
  • 复杂度为   l o g N \ log N  logN
  • N = 8 的算法
data = (data<<4) | (data>>4);  
data = ((data<<2) & 0xcc) | ((data>>2) & 0x33);  
data = ((data<<1) & 0xaa) | ((data>>1) & 0x55);
  • N位的蝴蝶算法(N为2的幂, int 是32位的,所以N 最大为32)
unsigned int bitReverse(unsigned int num, int N = 32)
{
	int M = 16;
	unsigned int mask = (unsigned int)(~0);
	while (M) {
		
		mask ^= mask >> M;
		
		if (2 * M <= N)
			num = ((num & mask) >> M) | ((num & ~mask) << M);
			
		M >>= 1;
	}
	return num;
}

位循环移动

流水灯常常需要将某个端口的位循环移动, 端口通常为8位

  • 循环移动N位
    直接将左右进行交换,这是数组所不能的
void circleRightShift(unsigned char& port, int n) {
	n %= 8;
	port = (port >> n) | (port << (8 - n));
}
void circleLeftShift(unsigned char& port, int n) {
	n %= 8;
	port = (port << n) | (port >> (8 - N));
}

lowbit运算

   l o w b i t lowbit lowbit 运算 是位运算中比较重要的运算方式。

lowbit概念

  定义一个函数 f = l o w b i t ( x ) f=lowbit(x) f=lowbit(x),这个函数的值等于 x x x二进制表达式中最低位的1所对应的值
  我们把数用二进制的形式来表示,如下(左为十进制数,右为二进制数) ( 2 ) 10 = ( 10 ) 2 (2)_{10} = (10)_{2} (2)10=(10)2 ( 5 ) 10 = ( 101 ) 2 (5)_{10} = (101)_{2} (5)10=(101)2 ( 24 ) 10 = ( 11000 ) 2 (24)_{10} = (11000)_{2} (24)10=(11000)2
  在上面 2, 5和24 的二进制表达式中,我们直接取最低位的1和后面的0,得到的值分别是 ( 10 ) 2 (10)_{2} (10)2 ( 1 ) 2 (1)_{2} (1)2 ( 1000 ) 2 (1000)_{2} (1000)2,即 2, 1, 8,所以得到
l o w b i t ( 2 ) = ( 10 ) 2 = 2 lowbit(2) = (10)_{2} = 2 lowbit(2)=(10)2=2 l o w b i t ( 5 ) = ( 1 ) 2 = 1 lowbit(5) = (1)_{2} = 1 lowbit(5)=(1)2=1 l o w b i t ( 24 ) = ( 1000 ) 2 = 8 lowbit(24) = (1000)_{2} = 8 lowbit(24)=(1000)2=8

  由上面的结果可以得出,假设一个数的二进制表示最低位的1在第 k k k(从右往左,最右边为第0位),那么,这个数的 l o w b i t lowbit lowbit值为 2 k 2^{k} 2k.
  如下图,最低位1在第3位上,则 l o w b i t lowbit lowbit 值为 2 3 = 8 2^3 = 8 23=8,也就是 ( 1000 ) 2 (1000)_2 (1000)2
在这里插入图片描述

lowbit运算的实现

  得到一个数的 l o w b i t lowbit lowbit值,即取出一个数的最低位,可通过如下操作:
  假设原来的数是a,对a进行取反就得到b,b再加1得到c,最后原数a和c进行位与操作,就得到了 l o w b i t lowbit lowbit值。
在这里插入图片描述
所以求 l o w b i t lowbit lowbit值的运算方法为:

lowbit = n & (~n + 1);

因为取反加1就是一个数的负数的补码,所以也写作

lowbit = n & (-n);

  当这个数是0,没有最低位1的时候,结果为0。

消去lowbit

一个数消去它的 l o w b i t lowbit lowbit 位,由上面的 l o w b i t lowbit lowbit 求法,直接减去它的 l o w b i t lowbit lowbit值 即可

n -= n & (-n);

还可以由 n 和 (n-1)位与 得到:
在这里插入图片描述

n &= (n-1);

通过不断进行消除 l o w b i t lowbit lowbit 操作,最后会变成0,并且 0 & (0-1) = 0,不会有变化。

求一个二进制数所包含的1的个数

这个就是不断进行消除 l o w b i t lowbit lowbit 操作,记录变成0所需要的操作次数即可。
因为是计算二进制的位数,所以参数为无符号整数。

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

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/qq_39151563/article/details/108305105

1. 两数之和-爱代码爱编程

1. 两数之和 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 +

KMP算法——next数组的计算-爱代码爱编程

KMP算法——next数组的计算 简介   KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特-莫里斯-普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现。 顺序

Python描述数据结构之并查集实战篇-爱代码爱编程

文章 前言1. LeetCode547:朋友圈2. LeetCode200:岛屿数量3. LeetCode990:等式方程的可满足性结束语 前言   有关并查集的知识及操作请参阅这篇博客。   本篇章所涉及到的题目均来源于力扣(LeetCode),著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。   LeetCod

三态电子商务公司算法岗面试题_使用逻辑回归预测宾馆下单的概率-爱代码爱编程

访谈问题 问题描述:房间共享公司(如Airbnb)希望帮助客房供应商 他们的房间价格合理。其中一个关键步骤是建立一个模型来预测 在一定条件下,一个房间的购买概率(由某些特征和日期描述) 数据发布在:三态电子商务公司算法岗面试题 (培训5万人次,测试数据2万人次) 目标:建立一个模型来预测每个测试数据的购买概率。我们将评估 根据结果的AUC建模(因此请给出

OJ习题详解 1222: EXTENDED LIGHTS OUT,2811: 熄灯问题 C++算法 枚举-爱代码爱编程

欢迎关注笔者,你的支持是持续更博的最大动力 目录 问题描述思路枚举改进:枚举局部代码相关内容其他 问题描述 1222: EXTENDED LIGHTS OUT(点击可看详细描述)中文版2811: 熄灯问题(点击可看中文描述) 简单来说,就是有一组5行6列的灯,每个灯有一个按钮,求一种按按钮方案,可使得所有灯都熄灭。 上

LeetCode 第 204 场周赛-爱代码爱编程

5499. 重复至少 K 次且长度为 M 的模式 垃圾题解 略 垃圾代码 class Solution: def containsPattern(self, arr: List[int], m: int, k: int) -> bool: print('ohhh') n = len(arr)