位运算–LC191– 位1的个数___LC231–2的幂___LC190– 颠倒二进制位__LC338– 比特位计数
位运算–LC191– 位1的个数___LC231–2的幂___LC190– 颠倒二进制位__LC338– 比特位计数
Java架构师必看
修改于 2023-09-25 16:13:32
修改于 2023-09-25 16:13:32
代码可运行
运行总次数：0
代码可运行
位运算的由来
在计算机里面，任何数据最终都是用数字来表示的（不管是我们平时用的软件，看的图片，视频，还是文字）。 并且计算机运算单元只认识高低电位，转化成我们认识的逻辑，也就是 0 1 。
这就是导致计算机里面任何数据最终都是用二进制（0 1）来保存的数字。只是我们平时看到的图片、文字、软件都只从二进行数字转化
而来的
例如:
利用上面提到的常用位操作：
x &= (x - 1)
从右往左，每次把最低位的 1 给打掉，并累加被打掉1的次数
如：
n : 0B101011
n - 1 : 0B101010
------------------
& : 0B101010
n : 0B101000
n - 1 : 0B100111
------------------
& : 0B100000例题
191. 位1的个数
难度简单330
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
提示：
- 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
- 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数
-3。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。解法一:
每次 打掉最后的一个 1 n &= n - 1 看有多少次
public class Solution {
public int hammingWeight(int n) {
int ret = 0;
while (n != 0) {
n &= n - 1;
ret++;
}
return ret;
}
}解法二:
mark = 1;
- 在当前位置 当前位置是否为 1
n & mark如果是一 计数加一 mark <<= 1向左移动一次…并判断左边的位置是否为一
int mark = 1;
for (int i = 0; i < 32; i++) {
if ((n & mark) != 0) {
ret++;
}
mark <<= 1;
}public class Solution {
public int hammingWeight(int n) {
int ret = 0;
int mark = 1;
for (int i = 0; i < 32; i++) {
if ((n & mark) != 0) {
ret++;
}
mark <<= 1;
}
return ret;
}
}231. 2的幂
难度简单294
给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
示例 1:
输入: 1
输出: true
解释: 2^0 = 1示例 2:
输入: 16
输出: true
解释: 2^4 = 16解题:
- 由于是2的幂 由二进制的以得到:
- 16 的 二进制为 0001 0000
- 可以利用二进制的位运算的
n&(n-1)打掉当前的数字二进制的最后一个零 判断是否零
class Solution {
public boolean isPowerOfTwo(int n) {
if (n > 0) {
//注意判断数的争取 负数, 零为非法数字
return (n&(n-1))==0;
}
return false;
}
}190. 颠倒二进制位
难度简单281
颠倒给定的 32 位无符号整数的二进制位。
示例 1：
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。相关解释动画
思路
- res 要的数字 左移一位 吧最后一个位置空出来 用来 存放n的 最后的一个数值
- 在 res 最后一位加上 n的 最后一个数字
- n 往 右边 移动一个 把 最右边的数字 打掉
public class Solution {
public int reverseBits(int n) {
int res = 0;
for (int i = 0; i < 32; i++) {
//res先往左移一位，把最后一个位置空出来，
//用来存放n的最后一位数字
res <<= 1;
//res加上n的最后一位数字
res |= n & 1;
//n往右移一位，把最后一位数字去掉
n >>= 1;
}
return res;
}
}338. 比特位计数
详细答案解说
难度中等688
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
输入: 2
输出: [0,1,1]示例 2:
输入: 5
输出: [0,1,1,2,1,2]方法一：直接计算
最直观的方法是对从 00 到 num 的每个数直接计算「一比特数」。
每个 int 型的数都可以用 32 位二进制数表示，只要遍历其二进制表示的每一位即可得到 1 的数目。
利用位运算的技巧，可以在一定程度上提升计算速度。按位与运算（&）的一个性质是：对于任意整数 x，令 x=x&(x−1)，该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 xx 重复该操作，直到 x 变成 0，则操作次数即为 x的「一比特数」。
class Solution {
public int[] countBits(int num) {
int[] bites = new int[num + 1];
for (int i = 0; i < num+1; i++) {
bites[i] = countOnes(i);
}
return bites;
}
private int countOnes(int i) {
int count = 0;
while (i > 0) {
i &= (i - 1);
count++;
}
return count;
}
}
动态规划——最低设置位
class Solution {
public int[] countBits(int num) {
int[] bits = new int[num + 1];
for (int i = 1; i < num + 1; i++) {
bits[i] = bits[i & (i - 1)] + 1;
}
return bits;
}
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
