基础算法篇——位运算
本次我们介绍基础算法中的位运算,我们会从下面几个角度来介绍:
- 位运算常用公式
- 二进制中1的个数
位运算常用公式
其实位运算的使用很常见但大多不难,经常都是套用公式
我们下面分别介绍两个公式:
- 求第n位数
// 求n的二进制的第k位数(将n向右移动k位,相当于将求解的位数放到个位,并且将其与1进行and运算)
n >> k & 1
- lowbit公式
// lowbit公式用来求该二进制的最后一位1的位置
lowbit(n) = n & -n;
// 其原理很简单,n是二进制数,-n是n取反,相当于-n和n的每一位都不相同
// 但是我们再加上1,就会导致n的最后一位1的位置变成了1.相当于所有位置的值都相反,但是只有最后一位1的位置都是1
二进制中1的个数
我们来简述一下题目:
- 给定一个长度为n的数列,请你求出数列中每个数的二进制表示中1的个数。
我们直接给出解答代码:
package cn.itcast.jvm.t1.gen;
import java.util.Scanner;
public class Sum1 {
public static void main(String[] args) {
// 读取n个数
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
while ( n-- > 0){
// 读入数
int x;
x = scanner.nextInt();
// 获得n后我们直接采用取n的最后一位1,并且将他减去并统计减去1的次数即可
int res = 0;
while (x > 0){
x -= lowbit(x);
res++;
}
System.out.println(res);
}
}
// lowbit操作
public static int lowbit(int x){
return x & -x;
}
}
结束语
好的,关于基础算法篇的位运算就介绍到这里,希望能为你带来帮助~
标签:运算,int,lowbit,基础,二进制,算法,公式 From: https://www.cnblogs.com/qiuluoyuweiliang/p/16871950.html