位运算
位运算
1.<<,>>,及<<<
<< : 左移运算符，num << 1,相当于num乘以2
>> : 右移运算符，num >> 1,相当于num除以2
>>> : 无符号右移，忽略符号位，空位都以0补齐
public class Main {
public static void main(String[] args) {
//注意类型长度，int类型的长度为32位
//1左移35位，已经溢出了,按常理来说应该会为负数
//但是位数超过32位时，会取余再左移
//左移35位就变为100
System.out.println(1<<35);
//1移位32就不变了
System.out.println(1<<32);
//这个就变负数了，为什么？即1000...000,首位负数，那都是负数了
System.out.println(1<<31);
//1左移3，即1000 = 8
System.out.println(1<<3);
}
} 2.判断奇偶数
在二进制形式下，偶数最后一位必为0，奇数最后一位必为1
- x&1=0 -->偶数
- x&1=1 -->奇数
3.例题
1-1000这个1000个数放在含有1001个元素的数组中，只有唯一的一个元素只重复，其他均只出现一次。每个数组元素只能访问一次，设计一个算法，将他找出来；不用辅助存储空间，能否设计一个算法实现？
import java.util.Arrays;
import java.util.Random;
public class Main {
public static void main(String[] args) {
int N = 1001;
int[] arr = new int[N];
for(int i=0; i<arr.length-1; i++){
arr[i]=i+1;
}
//最后一个数，是随机数
arr[arr.length-1]=new Random().nextInt(N-1)+1;
//随机下标
int index = new Random().nextInt(N);
swap(arr,index,arr.length-1);
System.out.println(Arrays.toString(arr));
/*
下面构造寻找方法
*/
//把数组所有的元素加起来，减去原来的，就剩下多出来的那个了
int total = 0;
for (int i = 0; i < arr.length ; i++) {
total += arr[i];
}
int usual = 0;
for (int i = 1; i <= N-1; i++) {
usual += i;
}
int outer = total - usual;
System.out.println(outer);
}
public static void swap(int[] arr, int index, int length) {
//暂存变量的值
int temp = arr[index];
arr[index] = arr[length];
arr[length] = temp;
}
} import java.util.Arrays;
import java.util.Random;
public class Main {
public static void main(String[] args) {
int N = 1001;
int[] arr = new int[N];
for(int i=0; i<arr.length-1; i++){
arr[i]=i+1;
}
//最后一个数，是随机数
arr[arr.length-1]=new Random().nextInt(N-1)+1;
//随机下标
int index = new Random().nextInt(N);
swap(arr,index,arr.length-1);
System.out.println(Arrays.toString(arr));
/*
下面构造寻找方法
*/
//把数组所有的元素加起来，减去原来的，就剩下多出来的那个了
int x1=0;
for(int i=0; i<=N-1; i++){
x1 = (x1^i);
}
for(int i=0; i<N; i++){
x1 = x1^arr[i];
}
System.out.println(x1);
System.out.println("============");
int[] helper = new int[N];
for(int i=0; i<N; i++){
helper[arr[i]]++;
}
for(int i=0; i<N; i++){
if(helper[i]==2){
System.out.println(i);
}
}
}
public static void swap(int[] arr, int index, int length) {
//暂存变量的值
int temp = arr[index];
arr[index] = arr[length];
arr[length] = temp;
}
} 2、一个数组里除了某一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现一次的数字。
public class Main {
public static void main(String[] args) {
int[] arr;
arr = new int[]{1,1,2,2,3,3,4,4,5,5,6};
int[] helper = new int[11];
for(int i=0; i<arr.length; i++){
helper[arr[i]]++;
}
for(int i=0; i<arr.length; i++){
if(helper[i]==1){
System.out.println(i);
}
}
}
} 3、请实现一个函数，输入一个整数，输出该数二进制表示中1的个数例：9的二进制表示为1001，有2位是1
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int X = scanner.nextInt();
System.out.println(Integer.toBinaryString(X));
int count=0;
for(int i=0; i<32; i++){
if((X&(1<<i))==(1<<i)){
count++;
}
}
System.out.println(count);
}
} 第二种解法：移动原数位将其与1对比
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int X = scanner.nextInt();
System.out.println(Integer.toBinaryString(X));
int count=0;
for(int i=0; i<32; i++){
if(((X>>>i)&1)==1){
count++;
}
}
System.out.println(count);
}
} 第三种解法：消除二进制上1的次数
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int X = scanner.nextInt();
System.out.println(Integer.toBinaryString(X));
int count=0;
while ( X!=0 ){
X=((X-1)&X);
count++;
}
System.out.println(count);
}
} 4、用一条语句判断一个整数是不是2的整数次方。
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int X = scanner.nextInt();
System.out.println(Integer.toBinaryString(X));
if(((X-1)&X)==0){
System.out.println("yes");
}else {
System.out.println("no");
}
}
} 4.将整数的奇偶位互换
public class Main {
public static void main(String[] args) {
int a = 9;
int b = m(9);
Assertions.assertThat(b).isEqualTo(6);
}
private static int m(int i){
int ou = i&0xaaaaaaaa;
int ji = i&0x55555555;
return (ou>>1)^(ji<<1);
}
} 5、给定一个介于0和1之间的实数，（如0.625），类型为 double，打印它的二进制表示（0.101，因为小数点后的二进制分别表示0.5,0.25.0.125.....)。
如果该数字无法精确地用32位以内的二进制表示，则打印“ERROR“
public class Main {
public static void main(String[] args) {
double num = 0.625;
StringBuilder sb = new StringBuilder("0.");
while(num>0){
//乘2：挪整
double r = num*2;
//判断整数部分
if(r>=1){
sb.append("1");
//消除整数部分
num = r - 1;
}else{
sb.append("0");
num = r;
}
if(sb.length()>34){
System.out.println("ERROR");
return;
}
}
System.out.println(sb.toString());
}
} 6、数组中只有一个数出现了1次，其他的数都出现了k次，请输出只出现了1次的数。
public class Main {
public static void main(String[] args) {
int[] arr = {2,2,2,9,7,7,7,3,3,3,6,6,6,0,0,0};
int len = arr.length;
char[][] kRadix = new char[len][];
int k = 3;
int maxLen = 0;
//转成k进制字符数组
//对于每个数字
for(int i = 0; i < len; i++){
//求每个数字的三进制字符串并翻转，然后转为字符数组
kRadix[i] = new StringBuffer(Integer.toString(arr[i], k)).reverse().toString().toCharArray();
if(kRadix[i].length > maxLen){
maxLen = kRadix[i].length;
}
}
int[] resArr = new int[maxLen];
for(int i=0; i<len; i++){
//不进位加法
for(int j=0; j<maxLen; j++){
if(j >= kRadix[i].length)
resArr[j] += 0;
else
resArr[j] += (kRadix[i][j] - '0');
}
}
int res = 0;
for(int i=0; i<maxLen; i++){
res += (resArr[i]%k)*(int)(Math.pow(k,i));
}
System.out.println(res);
}}
投递牛客等公司
