【Leetcode 程序员面试金典 05.01】插入 —— 位运算

简介: 位运算问题,只需要把 N 的 i 到 j 位都置 0 后再和 M 左移 i 位的结果进行按位或即可

面试题 05.01 插入

给定两个整型数字NM,以及表示比特位置的iji <= j,且从 0 位开始计算)。

编写一种方法,使M对应的二进制数字插入N对应的二进制数字的第i ~ j位区域,不足之处用0补齐。具体插入过程如图所示。

题目保证从i位到j位足以容纳M, 例如: M = 10011,则i~j区域至少可容纳5位。

示例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)

题目分析

简单的位运算问题,只需要把 N 的 i 到 j 位都置 0 后再和 M 左移 i 位的结果进行按位或即可

在 Java 语言中,int 类型的左移位数n≥32时,JVM 会将n32取模,以确保左移的位数在 n 在 [0,31] 之间。因此,需使用0xffffffff << j << 1

public int insertBits(int N, int M, int i, int j) {
   
   
    int mask = (0xffffffff << j << 1) + ((1 << i) - 1);
    return N & mask | M << i;
}

位运算基础知识

  1. 判断奇偶:

    • 奇:(x & 1) == 1  ⟺  (x & 1) != 0

    • 偶:(x & 1) == 0  ⟺  (x & 1) != 1

  2. 乘(或除)以 2 的幂次:

    • x >> n  ⟺ x / 2^n

    • x << n  ⟺ x * 2^n

  3. 去除最后一位 1:x & (x - 1)

  4. 得到最后一位 1:x & -x

  5. 判断 2 的幂次:x & (x - 1) == 0

  6. 交换两个数:a ^= b; b ^= a; a ^= b;

  7. 交换符号:~x + 1  ⟺  -x

  8. 取绝对值:(x ^ x >> size(x) - 1) - (x >> size(x) - 1)  ⟺ x < 0 ? -x : x

  9. 构造 n 个 1:(1 << n) - 1

  10. 将最左边的 n 位清零:x & (~0 << n)

  11. 获取 x 的第 n 位值(0 或 1):(x >> n) & 1

  12. 获取 x 的第 n 位的幂值:x & (1 << n)

  13. 仅将第 n 位置为 1:x | (1 << n)

  14. 仅将第 n 位置为 0:x & (~(1 << n))

  15. 将 x 最高位至第 n 位(含)清零:x & ((1 << n) - 1)

  16. 将第 n 位至第 0 位(含)清零:x & (~((1 << (n + 1)) - 1))

  17. 取反第 n 位:x ^ (1 << n)

  18. 异或满足交换律、结合律:a ^ b ^ a = b ^ (a ^ a) = b ^ 0 = b

相关文章
|
29天前
|
算法
【数组相关面试题】LeetCode试题
【数组相关面试题】LeetCode试题
|
1月前
|
存储 Java
面试官:你真的搞清位运算了么?
面试官:你真的搞清位运算了么?
31 0
|
1月前
力扣面试经典题之哈希表
力扣面试经典题之哈希表
17 0
|
1月前
|
存储
力扣面试经典题之数组/字符串
力扣面试经典题之数组/字符串
21 0
|
3月前
|
存储 算法 程序员
【Leetcode 程序员面试金典 01.01】判定字符是否唯一 —— 位运算|哈希表
可以使用哈希表或位运算来解决此问题:由题可知s[i]仅包含小写字母,int[26]即能表示字符的出现次数;
|
1月前
力扣面试经典题之二叉树
力扣面试经典题之二叉树
14 0
|
2月前
|
JavaScript 前端开发 C语言
leetcode每日一题 2021/4/2 面试题 17.21. 直方图的水量
leetcode每日一题 2021/4/2 面试题 17.21. 直方图的水量
22 0
|
30天前
|
机器学习/深度学习 人工智能 算法
LeetCode刷题--- 面试题 01.07. 旋转矩阵(原地旋转+翻转替旋转)
LeetCode刷题--- 面试题 01.07. 旋转矩阵(原地旋转+翻转替旋转)
|
1月前
|
算法 测试技术 索引
力扣面试经典题之数组/字符串(二)
力扣面试经典题之数组/字符串(二)
13 0
|
2月前
|
运维 算法 程序员
程序员去国企:长城资产IT岗位秋招面试记录
【2月更文挑战第7天】本文介绍2024届秋招中,中国长城资产管理股份有限公司的信息技术岗岗位一面的面试基本情况、提问问题等~