这里我假设读者有二进制的思维,知道(3)~10~=(011)~2~将十进制转换为二进制的方法
关于上面的说明,这里还是补充一下,因为并不是所有人都了解位运算 <<的运算规则:按二进制形式把所有的数字向左移动对应的位数,高位移出(舍弃),低位的空位补零。以3<<2为例,首先把3转换为二进制数字0000 0000 0000 0000 0000 0000 0000 0011(int型是4个字节,1个字节8位,所以int是32位),然后将上面的二进制数字向左移动2位后面补0得到0000 0000 0000 0000 0000 0000 0000 1100 在数字没有溢出的前提下,对于正数和负数,左移一位都相当于乘以2的1次方,左移n位就相当于乘以2^n^ >>的运算规则:按二进制形式把所有的数字向右移动对应位数,低为移出(舍弃),高位的空位补符号位,即正数补零,负数补1.以11>>2为例,首先把11转换为二进制数字0000 0000 0000 0000 0000 0000 0000 1011,然后把低位的两个数字移出,因为该数字是正数,所以在高位补零,则得到的最终结果是0000 0000 0000 0000 0000 0000 0000 0010 右移一位相当于除以2,右移n位相当于除以2^n^ >>>运算规则:和>>大致相同,区别在于不论是正数还是负数,高位都补零
1-1000这1000个数放在含有1001个元素的数组中,只有唯一的一个元素重复,其它均只出现一次,每个数组元素只能访问一次,设计一个算法,将它找出来,不用辅助存储空间 位运算总共就那么几条性质,该记的还是要记。假设一个数组中的值分别是1,2,3,4,2,2是重复的元素,那么应该怎么把它挑出来呢,最开始想到的方法肯定是两重循环枚举,时间复杂度是O(n^2^),不太好,想想怎么用位运算解决这道题,根据a^a=0,a^0=a这两条性质,我们可以把数组中的元素全部异或起来,然后再异或一遍不重复的所有元素,就是(1^2^3^4^2)^(1^2^3^4),这样把它们凑起来,最后结果就应该是2^2^2=2^0=2,正好是要找的重复元素
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = 1001,sum1 = 0,sum2 = 0;
int[] arr = new int[n];
for(int i = 0;i < n - 1;i++) {
arr[i] = i + 1;
sum1 ^= arr[i];
}
arr[n - 1] = new Random().nextInt(n);//随机数,1-n
sum2 = sum1 ^ arr[n - 1];
int idx = new Random().nextInt(n);//随机选取一个下标
{//交换
int t = arr[idx];
arr[idx] = arr[n - 1];
arr[n - 1] = t;
}
/*for(int i = 0;i < n;i++) {
System.out.print(arr[i] + " ");
}*/
System.out.println(sum1 ^ sum2);
}
}
一个数组里除了某一个数字以外,其他的数字都出现了两次。请写程序找出这个只出现一次的数字 这道题比上一道题还简单,这道题直接将所有的值全部异或起来,得到的结果就是落单的数了
请实现一个函数,输入一个整数,输出该二进制表示中1的个数 第一种方法:假设这个数是3,其二进制为011,首先将011&001,判断得出来的结果是否等于001,如果等于,说明这个第1位是1;然后将011&010,判断得出来的结果是否等于010,如果等于,说明这个第2位是1,一直进行下去,判断31位
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int cnt = 0;
for(int i = 0;i < 32;i++)
if(((1 << i) & n) == (1 << i))
cnt++;
System.out.println(cnt);
}
}
第二种方法:只让要测验的数向右移。假设这个数是3,其二进制为011,首先将011&001,判断得出来的结果是否等于001,如果等于,说明这个第1位是1;然后将001&001,判断得出来的结果是否等于001,如果等于,说明这个第2位是1,一直进行下去,判断31位
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int cnt = 0;
for(int i = 0;i < 32;i++)
if(((n >>> i) & 1) == 1)
cnt++;
System.out.println(cnt);
}
}
第三种方法:还是假设这个数是3,那我们让3变成0的过程中肯定是要消掉1的,消掉多少次1,就表示3的二进制中有多少个1。关键就在于,如何消掉011中的1,我们首先让011减1,那么011就变成了010,然后让011&010,就得到了010,然后再让010减1,那么010就变成了001,然后让010&001,就得到了000,转换成伪代码的形式就是,a = (a - 1) & a,它的效果就是消掉最低位上的1,依次消掉所有最低位上的1,最后不久变成了0吗
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int cnt = 0;
while(n != 0) {
n = (n - 1) & n;
cnt++;
}
System.out.println(cnt);
}
}
用一条语句判断一个整数是不是2的整数次方 这道题比较好想,判断一个数是不是2的整数次方,其实就是判断这个数的二进制数是不是有且仅有一个1,这个和上面那道题很相似,仔细想想,直接给出代码了
if((n & (n - 1)) == 0)
假设这个数是9,二进制就是1001,那么得到的结果就是0110 首先我们需要两个个数
a = 0x55555555
b = 0xaaaaaaaa
a和b都是16进制数,转换为二进制分别是0101 0101 0101...,1010 1010 1010...(因为1010对应的十进制是10,而10在16进制中是a,0101也同理),然后将需要改变的数n分别对a和b进行&运算得到c和d,然后将c向左移1位,将d向右移1位,再分别进行异或,就得到所求结果,看下面示例
n = 1001
a = 0101
b = 1010
c = n & a = 0001
d = n & b = 1000
res = (c << 1) ^ (d >> 1) = 0110