位操作面试题集锦
都是从网上找的，自己按照参考答案写了一遍，这里汇总一下，留着复习。也希望路过的挑刺指正。
左移位：将运算数的二进制码整体（包括符号位）左移指定位数，左移之后的空位用0补充
右移位：将运算数的二进制码整体右移指定位数，右移之后的空位用符号位补充(正数用0补充，负数用1补充)
1 写一个BitUtil类，设置0、1经常用到。
public class BitUtil{
public static int setBit(int num,int index,boolean b){
if(b) return (num | (1<<index));
int mask = ~(1<<index); //~ 是按位取反
return (num & mask);
}
public static boolean getBit(int num,int index){
int mask = num & (1<<index);
return (mask != 0);
}
}
2 统计一个整数二进制式‘1’的个数
public static void count1(int n){
int num=n;
int count=0;
//解法1：每次右移，和1<<31 & 运算，不为0，则该位是1
/**while(num!=0){
if((num&(1<<31))!=0) count++;
num=(num<<1);
}**/
//解法2： n&(n-1)的效果：n的二进制位从右往左第一个1变成0，该位置右侧全部变成1
// 110100 & 110011 = 110000，这样每次消掉一个1
// -2147483648-1=2147483647 即0x80000000-1=0x7fffffff 二者相&为0
while(num!=0){
num&=(num-1);
System.out.println(num);
count++;
}
System.out.println(n+"有"+count+"个1");
}
3 实现方法将一个整数中的偶数位和奇数位交换。(是交换二进制位) 例如：将0位和1位交换，2位和3位交换
public static void swapOddEven(int num){
//注释的语句方法对于负数不适用，因为负数右移时，用1填充 例如10****，
//本来应该变成01****为正数，但是由于用了1填充， | 运算后必然还是负的
//所以应该先右移，然后用0把填充的1替换掉
//int result = ((0xaaaaaaaa & num)>>1)|((0x55555555 & num)<<1);
int result = ((num>>1)&0x55555555)|((0x55555555 & num)<<1);
System.out.println(result);
}
4给定一个32bit的数值，如果输出比特位反转后的值， 如对于4bit的二进制值1011，翻转后为1101。（第1位放32位，第1位放第32位……，第32位放第一位）
要求复杂度O(lgn),n 为比特位数。
public static void reversBits(int num){
/**土办法，达不到时间要求
for(int i=0;i<32;i++){
int result=0;
result=((result<<1)|(num&1));
num=num>>1;
}
**/
/**采用交换的方法，先两位对调，然后4位…… **/
num = ((num>>1)&0x55555555)|((num&0x55555555)<<1);
num = ((num>>2)&0x33333333)|((num&0x33333333)<<2);
num = ((num>>4)&0x0f0f0f0f)|((num&0x0f0f0f0f)<<4);
num = ((num>>8)&0x00ff00ff)|((num&0x00ff00ff)<<8);
num = ((num>>16)&0x0000ffff)|((num&0x0000ffff)<<16);
System.out.println("result"+num);
}
5 实现函数计算将整数从A变成B需要变动几位 例如 输入:31,14 输出 2
public static void changeA2B(int a,int b){
int count=0;
/**
for(int i=0;i<32;i++){
if(BitUtil.getBit(a,i)!=BitUtil.getBit(b,i)) count++;
}
**/
//或者使用Xor
for(int c=(a^b);c>0;c=(c>>1)){ // c=(c>>1)有没有简写方式？
count+=(c&1);
}
System.out.println("需要改动"+count+"次");
}
6 一个数组A[1，n]能容纳n个数字，现将0到n这n+1个数字，随机的放入到数组中。 最后会有一个数字没有进入数组。现在让你找出这个数字。 但是有如下的限制，不能直接访问数组的整个元素，只能访问“A[i]的第j位”。 写出代码找出该元素。能否将时间复杂度控制在O(n)。
/** 解法1： 借鉴编程珠玑 时间复杂度 n+n/31+31 = O(n)
解法2： 讲0~n按照二进制码表示，则最低位是0,1,0,1……，如果n奇数count(0)>count(1),n是偶数count(0)=count(1)
所以如果确实的数为K：
若K的最低位是0 当n为奇数时count(0)=count(1)
当n为偶数时count(0)=count(1)-1
若K的最低位是1 当n为奇数时count(0)=count(1)-2
当n为偶数时count(0)=count(1)-1
这样每次可以删除一半的数，时间复杂度O(n)+O(n/2)+O(n/4)+…… 但是每次都需要讲末尾为0、1的数再存储
所以感觉效率不是很好
**/
public static void findTheMissOne(int [] array){
int miss=0;
int n = array.length;
int memArray [] = new int[(n+30)/31];
System.out.println(memArray.length);
for(int i=0;i<n;i++){
int curr = array[i];
memArray[curr/31] = BitUtil.setBit(memArray[curr/31],curr%31,true); //这样调用setBit总感觉很别扭
}
int j=0;
for(;j<memArray.length;j++){
if( (memArray[j] | (1<<31)) != -1) break;
}
int k=0;
for(;k<31;k++){
if(!BitUtil.getBit(memArray[j],k)) break;
}
miss = j*31+k;
System.out.println("the missing num is :"+miss);
}
http://blog.csdn.net/coder_xia/article/details/7922077