首页 > 其他分享 >位运算合集

位运算合集

时间：2024-02-25 19:57:25浏览次数：21  
标签：11 运算 示例 二进制 题解 int 异或 合集

目录

题目

位运算分为两类：

1.逻辑位运算符

(1)位与( & )
当 两位 都为1时，结果为1
(2) 位或( | )
当且仅当两位都为0时，结果为0
(3) 异或( ^ )
当且仅当两位不同时，结果为1
(4) 按位取反( ~ )
1---0  0---1

2.位移运算符

(1)左移(<<)
	末位补0。左移是指的二进制这串数字往左移动
(2)右移(>>)
	负数补1，非负数补零

231. 2 的幂

  • 给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

示例 1：

输入：n = 5
输出：false

示例 2：

输入：n = 16
输出：true
解释：24 = 16

题解

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False
        else:
            if (n & (n-1))==0:
                return True
            else:
                return False

342. 4的幂

  • 给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x

示例 1：

输入：n = 16
输出：true

示例 2：

输入：n = 5
输出：false

题解

  • 当一个数是2的偶数次幂（比如24可以化为42），当为2的奇数次幂（比如2^3不可以化为4的幂）。可以用n除以3，如果余1则为2的偶数次幂，如果余2则为2的奇数次幂。
  • 所以本题只需要判断n是否为2的幂，并且用除以3通过余数判断是2的偶数次幂来解决。
class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n <= 0:
            return False
        else:
            if (n & (n-1))==0 and n%3==1:
                return True
            else:
                return Falsee

191. 位1的个数

  • 编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。

示例 1：

输入：n = 00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2：

输入：n = 11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

题解

  • n & (n - 1) ，这个代码可以把 n 的二进制中，最后一个出现的 1 改写成 0。使得 n 变成 0 的操作次数，就是 n 的二进制中 1 的个数。
  • 与&：全1为1。比如n=3,则n & (n - 1)：3&2=11&10=10可以发现进行一次n & (n - 1)后11的最后一位1变成了0即10。解决本题n中1的个数只需要统计n变成0需要几次n & (n - 1)即可
class Solution(object):
    def hammingWeight(self, n):
        res = 0
        while n:
            res += 1
            n &= n - 1
        return res

面试题 16.01. 交换数字(中)

  • 编写一个函数，不用临时变量，直接交换numbers = [a, b]中a与b的值。

示例 1：

输入: numbers = [1,2]
输出: [2,1]

题解

  • 异或^:a ^ 0 = a;a ^ a=0，并且满足交换律结合律
  • 例子交换a,b:

a = a ^ b
b = a ^ b=(带入上面a)a ^ b ^ b=(结合律)a ^ 0=a
a = a ^ b =a ^ b ^ a =(带入上面a,b)a ^ a ^ b=(交换律)0 ^ b=b

class Solution:
    def swapNumbers(self, numbers: List[int]) -> List[int]:
        numbers[0]=numbers[0]^numbers[1]
        numbers[1]=numbers[0]^numbers[1]
        numbers[0]=numbers[0]^numbers[1]
        return numbers

136. 只出现一次的数字

  • 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
    你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1：

输入：nums = [2,2,1]
输出：1

示例 2：

输入：nums = [4,1,2,1,2]
输出：4

题解

  • 异或^:a ^ 0 = a;a ^ a=0，并且满足交换律结合律
  • 只需要对数组里面的元素做异或操作，只要有相同的都会为0，最后剩下的那个与0异或为他本身，返回即可
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        x=0
        for num in nums:
            x ^= num
        return x

461. 汉明距离

  • 两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
    给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：

输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)
..........↑....↑
上面的箭头指出了对应二进制位不同的位置。

示例 2：

输入：x = 3, y = 1
输出：1

题解

  • 异或^:a ^ 0 = a;a ^ a=0
  • 二进制都是0/1，x ^ y相同的位置0，不同的位置为1，汉明距离要求的是二进制不同的位置数目，转化为统计异或后数的1的个数。
class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        n=x^y
        res  = 0
        while n:
            res+=1
            n &=n-1
        return res

693. 交替位二进制数

  • 给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

示例 1：

输入：n = 5
输出：true
解释：5 的二进制表示是：101

示例 2：

输入：n = 7
输出：false
解释：7 的二进制表示是：111.

示例 3：

输入：n = 11
输出：false
解释：11 的二进制表示是：1011.

题解

  • 与&:都为1才为1
  • n的二进制与3的二进制11&，满足要求的是01&11=01或10&11=10，如果n为00则00&11=00，n为11则11&11=11，当与的结果为00或11时（十进制为0、3）返回False，其他返回True，并且要对n的二进制循环右移检查
  • 右移是指n的二进制这串数字往右移动
class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        while n:
            if n&3==3 or n&3==0:
                return False
            n >>=1
        return True

1863. 找出所有子集的异或总和再求和

  • 一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。
    例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。
    给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。

示例 1：

输入：nums = [1,3]
输出：6
解释：[1,3] 共有 4 个子集：

  • 空子集的异或总和是 0 。
  • [1] 的异或总和为 1 。
  • [3] 的异或总和为 3 。
  • [1,3] 的异或总和为 1 XOR 3 = 2 。
    0 + 1 + 3 + 2 = 6

示例 2：

输入：nums = [5,1,6]
输出：28
解释：[5,1,6] 共有 8 个子集：

  • 空子集的异或总和是 0 。
  • [5] 的异或总和为 5 。
  • [1] 的异或总和为 1 。
  • [6] 的异或总和为 6 。
  • [5,1] 的异或总和为 5 XOR 1 = 4 。
  • [5,6] 的异或总和为 5 XOR 6 = 3 。
  • [1,6] 的异或总和为 1 XOR 6 = 7 。
  • [5,1,6] 的异或总和为 5 XOR 1 XOR 6 = 2 。
    0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

示例 3：

输入：nums = [3,4,5,6,7,8]
输出：480
解释：每个子集的全部异或总和值之和为 480 。

题解

  • 与&:都为1才为1
  • n的二进制与3的二进制11&，满足要求的是01&11=01或10&11=10，如果n为00则00&11=00，n为11则11&11=11，当与的结果为00或11时（十进制为0、3）返回False，其他返回True，并且要对n的二进制循环右移检查
  • 右移是指n的二进制这串数字往右移动
class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        i, total = 0, 0  # 初始化计数器和总和变量
        #(1 << len(nums)) 将数字1左移len(nums)位，得到一个二进制数。对于长度为4的列表，即 (1 << 4)，结果为16，表示列表的所有子集数量。
        while i < (1 << len(nums)):  # 外循环遍历所有可能的子集
            j = 0  # 初始化内循环的索引
            ans = 0  # 初始化当前子集的异或和
            while j < len(nums):  # 内循环遍历nums列表中的每个元素
            #例如，对于j=2，(1 << 2) 的结果是 4，二进制表示为 100。检查变量i的第j位是否为1
                if i & (1 << j):  # 检查当前子集中的位是否为1
                    ans ^= nums[j]  # 对当前子集的元素进行异或运算
                j += 1  # 增加内循环的索引
            total += ans  # 将当前子集的异或和累加到总和变量中
            i += 1  # 增加外循环的索引，继续下一个子集的计算
        return total  # 返回所有子集的异或和作为结果

371. 两整数之和（中）

  • 给你两个整数 a 和 b ，不使用 运算符 + 和 - ​​​​​​​，计算并返回两整数之和。

示例 1：

输入：a = 1, b = 2
输出：3

示例 2：

输入：a = 2, b = 3
输出：5

题解

  • 例子：

初始状态：
a = 2，二进制表示为 0010
b = 3，二进制表示为 0011
第一轮递归调用：
a ^ b = 0010 ^ 0011 = 0001
(a & b) << 1 = (0010 & 0011) << 1 = 0010 << 1 = 0100
递归调用 self.getSum(0001, 0100)。
第二轮递归调用：
a ^ b = 0001 ^ 0100 = 0101
(a & b) << 1 = (0001 & 0100) << 1 = 0000 << 1 = 0000
递归调用 self.getSum(0101, 0000)。
第三轮递归调用：
a ^ b = 0101 ^ 0000 = 0101
(a & b) << 1 = (0101 & 0000) << 1 = 0000 << 1 = 0000
递归调用 self.getSum(0101, 0000)。
此时，b等于0，满足终止条件，递归结束。
最终的结果为0101，即5。

class Solution:
    def getSum(self, a: int, b: int) -> int:
        # 如果b等于0，则不需要进位，直接返回a
        if b == 0:
            return a
        # 使用递归调用来计算和
        return self.getSum(a ^ b, (a & b) << 1)
  • 超出内存限制，由于python整数类型为无限长整数类型.我们需要将结果限制在32位范围内
class Solution:
    def getSum(self, a: int, b: int) -> int:
        MASK = 0xFFFFFFFF#由于 0xFFFFFFFF 的所有位都是1，与任何整数进行 & 操作都会保留该整数的低32位，并将高位清零
        # 如果b等于0，则不需要进位，直接返回a
        if b == 0:
            return a if a < 0x80000000 else ~(a ^ MASK)# 如果a小于0x80000000（负数的最高位为1），返回a；否则返回a和0xFFFFFFFF的按位异或取反结果
        # 使用递归调用来计算和
        return self.getSum((a ^ b)& MASK, ((a & b) << 1)& MASK)#通过 & 0xFFFFFFFF 将结果限制在32位范围内

面试题 05.01. 插入

  • 给定两个整型数字 N 与 M，以及表示比特位置的 i 与 j（i <= j，且从 0 位开始计算）。
    编写一种方法，使 M 对应的二进制数字插入 N 对应的二进制数字的第 i ~ j 位区域，不足之处用 0 补齐。

示例 1：

输入：N = 1024(10000000000), M = 19(10011), i = 2, j = 6
输出：N = 1100(10001001100)

示例 2：

输入： N = 0, M = 31(11111), i = 0, j = 4
输出：N = 31(11111)

题解

  • &：两位都为1时，结果为1；|：两位都为0时，结果为0
  • 1.先把N的i-j位置全部归0（与想归0的位置为0其他位为1的数&）
  • 2.把M塞进N（将M左移i位，与N位或|）
class Solution:
    def insertBits(self, N: int, M: int, i: int, j: int) -> int:
        for k in range(i,j+1):
            N &=~(1<<k)#~(1 << k) 的含义是将数字1左移k位，然后对其进行按位取反。这将生成一个二进制表示中只有第k位为0，其余位都为1的数。
        return N | (M<<i)

标签：11,运算,示例,二进制,题解,int,异或,合集
From： https://www.cnblogs.com/lushuang55/p/18032309

相关文章

  • Java基础07：基本运算符
    运算符1.Java语言支持如下运算符：1.1算术运算符：+，-，*，/，%，++，--1.2赋值运算符：=1.3关系运算符：>，<，>=，==，!=instanceof1.4逻辑运算符：&，|，^，~，>>，<<，>>>(了解)1.5条件运算符？：1.6扩展赋值运算：+=，-=，*=，/= ......
  • 《程序是怎样跑起来的》第三章“计算机进行小数运算时出错的原因”
    当我们使用计算机进行小数运算时，可能会遇到一些意想不到的错误。这些错误并非计算机的缺陷，而是由于其内在的特性所导致的。深入了解这些原因，有助于我们更好地理解计算机运算的局限性和应对策略，从而在编程和数据处理时更加得心应手。计算机在进行小数运算时出错的原因包括二进......
  • 第三章 计算机进行小数运算
    用二进制数来表示整数和整数的方法有很大不同，例如：0次幂前面的位的位权按照1次幂、2次幂……的方式递增，0次幂以后的位的位权按照-1次幂、-2次幂……的方式递减（这一规律在十进制数和16进制数中也同样适用）。在了解了将二进制数表示的小数转化成10进制数的方法后，计算机运算出错的原因......
  • linux--初学者的常用命令合集(频率比较高的)
     sudosuroot    打开root权限passwdroot     修改root密码ctrlshift+      字符变大ctrl-          字符变小cd.           返回本目录cd..           返回上一级目......
  • 计算机进行小数运算时出错的原因
    通过此章的学习我了解的计算机出错的几个重大原因，以及什么是浮点数，让我对计算机有了更加深刻的认知和理解，我也了解到如何在实际程序中确认和如何避免计算机出错计算机运算出错的原因计算机之所以会出现运算错误，是因为“有一些十进制数的小数无法转换成二进制数”。代码清单3-1......
  • C# 的运算符和作用域
    //C#运算符//表达式表达式有操作数（operand）和运算符（operator）构成；//常见的运算符+-*/和new//x??y如果x为null，则计算机过为y否则计算结果为x；//匿名函数(lamba表达式)//前置的++直接执行后......
  • 数据库基础4 关系代数运算
    基本操作前提条件：并相容性是并、差、交等关系代数操作的前提参与运算的两个关系及其相关属性之间必须又一定的对应性、可比性或关联性两个关系的属性数量必须相同对于任意i，关系R的第i个属性必须与另一个关系的第i个属性的域相同（数据类型、取值范围）一、传统集合运算并......
  • C++ 令人无语/好用的语法合集
    此贴用来总结一些傻逼C++语法，或者坑了我很久的写法。1、（坑）重载>,<,==时，千万不要使用pair为基的typedef!!!!!!pii的max不受你的重载影响，它自己有自己的max，然后typedef和define是相同的，基本可以看做直接替换，不会对作用域/命名做区分。2、（坑）lower_bound(..,..,{x......
  • ES6扩展运算符（...）
    在ES6中，扩展运算符（...）是一种用来展开数组和对象的语法。它可以将一个数组或对象展开，以便在函数调用、数组字面量或对象字面量中使用。1//1.在数组中的应用：2letarr=[1,2,245,6]3letarr1=[...arr,3,5,7]4console.log(arr1)//[1,2,245,6,3,5,7]56......
  • C++的箭头运算符
    以前学类的时候，一个指针指向类的实例，当我们想通过指针访问某些类的成员的时候，书上直接告诉你，使用->来访问这些成员，不能用.运算符。我以前也是默默接受了这个观点，平时也没细想，今天才知道是怎么回事。string*p=string("hello");*p.empty();//错误。会先执行p.empty()，之后再......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99