面试题5.1：给定两个32位的整数N与M，以及表示比特位置的i与j。编写一个方法，将M插入N，使得M从N的第j位开始，到第i位结束。假定从j位到i位足以容纳M，也即若M=10011，那么j与i之间至少可容纳5个位。例如，不可能出现j=3和i=2的情况，因为第3位和第2位之间放不下M。
输入：N=10000000000，M=10011，i=2,j=6，最后是第0位
输出：N=10001001100
package cc150.bit;
public class UpdateBits {
//面试题5.1：给定两个32位的整数N与M，以及表示比特位置的i与j。
//编写一个方法，将M插入N，使得M从N的第j位开始，到第i位结束
public static void main(String[] args) {
// TODO 自动生成的方法存根
UpdateBits ub = new UpdateBits();
System.out.println(ub.updateBits(1,1,2,4));
}
public int updateBits(int n,int m,int i,int j){ //M插入N,i为右边第i位，j为右边第j位
int allOnes = ~0; //一串1 ,~0连符号位都是１
int left = allOnes << (j+1);
int right = (1 << i) -1;
int mask = left | right; //置零了从第i位到第j位
int n_clear = n & mask; //把n置零
int m_shifted = m << i; //把ｍ左移动i位对其
//return Integer.toBinaryString(mask);
return n_clear | m_shifted; //返回合并后的值
}
}
面试题5.2: 给定一个介于0和1之间的实数（如0.72），类型为double，打印它的二进制表示。如果该数字无法精确地用32位以内的二进制表示，则打印“ERROR”。
package cc150.bit;
public class BinDecimal {
//面试题5.2: 给定一个介于0和1之间的实数（如0.72），类型为double，打印它的二进制表示。
public static void main(String[] args) {
// TODO 自动生成的方法存根
BinDecimal bd = new BinDecimal();
System.out.println(bd.printBin(0.625)); //0.5+0.125
}
public String printBin(double num) {
// write code here
if(num >= 1 || num <= 0)
return "ERROR";
StringBuffer bf = new StringBuffer();
while(num > 0){
if(bf.length() >= 32)
return "ERROR";
double result = num * 2; //在循环中不断×2，如果大于1就减去1
if(result >=1){
bf.append(1);
num = result - 1;
}else{ //如果没有大于1，就把result赋值给num，继续×2
bf.append(0);
num = result;
}
}
return "0."+bf.toString();
}
}
面试题5.3：给定一个正整数，找出与其二进制表示中1的个数相同、且大小最接近的那两个数（一个略大，一个略小）。
package cc150.bit;
public class CloseNumber {
public static void main(String[] args) {
// TODO 自动生成的方法存根
CloseNumber cn = new CloseNumber();
System.out.println(Integer.toBinaryString(cn.getPre(13948)));
System.out.println(Integer.toBinaryString(13948));
}
public int[] getCloseNumber(int x) {
// write code here
int[] result = null;
int a = getPre(x);
int b = getNext(x);
if(a != -1 && b != -1){
result = new int[2];
result[0] = a;
result[1] = b;
return result;
}
else if(a != -1 && b == -1){
result = new int[1];
result[0] = a;
return result;
}
else if(a == -1 && b != -1){
result = new int[1];
result[0] = b;
return result;
}
return result;
}
public int getNext(int n){
int c = n;
int c0 = 0; //计算最右边的1的位置，都是从0开始计数
int c1 = 0; //计算非尾部的最右边的0的位置，是去掉尾部的0之后的位置
while(((c & 1) == 0) && (c != 0)){ //当最后一位是1或者c等于0的时候停止
c0++;
c >>= 1; //右移并用1填充
}
while((c & 1) == 1){ //因为上一步已经把最右边所有的零去掉，所以这里计算最右边的0的位置
c1++;
c >>= 1;
}
if(c0 + c1 == 31 || c0 + c1 == 0)
return -1;
int p = c0+c1; //计算非尾部的最右边的0的位置
n |= (1 << p); //把非尾部的最右边的0翻转成1，计算大于的那个值
n &= ~((1 << p) - 1); //将p右边的所有位清0
n |= (1 << (c1-1)) - 1; //在右边插入(c1-1)个1
return n;
}
public int getPre(int n){
int temp = n;
int c0 = 0; //计算最右边1的位置，是去掉尾部的1之后的位置
int c1 = 0; //计算最右边0的位置
System.out.println("n="+Integer.toBinaryString(n));
while((temp & 1) == 1){ //计算最右边0的位置
c1++;
temp >>= 1;
}
System.out.println("c1="+Integer.toBinaryString(c1));
if(temp == 0)
return -1;
while(((temp & 1) == 0) && (temp != 0)){//当最后一位是1或者c等于0的时候停止
c0++; //计算最右边1的位置，去掉了尾部的1之后的位置
temp >>= 1;
}
System.out.println("c0="+Integer.toBinaryString(c0));
int p = c0+c1; //计算最右边1的位置
n &= ((~0) << (p+1)); //将p右边的所有位清0（包括p），p是非尾部的最右边的1
System.out.println("清零后："+Integer.toBinaryString(n));
int mask = (1 << (c1 + 1)) - 1; //c1+1个1，清零之后，需要补充c1+1个1
System.out.println("补充1的个数："+Integer.toBinaryString(mask));
n |= (mask << (c0 - 1)); //需要补充的1多大能是多少，然后和清零后的合并
System.out.println("需要补充的1多大能是多少："+Integer.toBinaryString(mask << (c0 - 1)));
return (n);
}
}
面试题5.4：解释代码 ((n&(n-1)) == 0) 的具体含义。
面试题5.5：编写一个函数，确定需要改变几个位，才能将整数A转成整数B。
package cc150.bit;
public class Transform {
public static void main(String[] args) {
// TODO 自动生成的方法存根
Transform tf = new Transform();
System.out.println(tf.calcCost(2,1));
}
public int calcCost(int A, int B) {
// write code here
int count = 0;
int c = A ^ B;
for(int i=c;i != 0;i=i >> 1)
count += i & 1;
return count;
}
}
面试题5.6：编写程序，交换某个整数的奇数位和偶数位，使用指令越少越好（也就是说，位0与位1交换，位2与位3交换，依次类推）。
package cc150.bit;
public class Exchange {
public static void main(String[] args) {
// TODO 自动生成的方法存根
Exchange ec = new Exchange();
System.out.println(ec.exchangeOddEven(2));
}
public int exchangeOddEven(int x) {
// write code here
return ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1); //0xaaaaaaaa是提取1010，0x55555555是提取0101
//1010右移，0101左移
}
}
面试题5.7：数组A包含0到n的所有整数，但其中缺了一个。在这个问题中，只用一次操作无法取得数组A里某个整数的完整内容。此外，数组A的元素皆以二进制表示，唯一可用的访问操作是“从A[i]取出第j位数据”，该操作的时间复杂度为常数。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
package cc150.bit;
public class Finder {
public static void main(String[] args) {
// TODO 自动生成的方法存根
int[][] a = {{0},{1,0},{0,1},{0,0,1},{1,0,1}}; //少了1,1
Finder fd = new Finder();
System.out.println(fd.findMissing(a,5));
}
public int findMissing(int[][] numbers, int n) {
// write code here
for(int i = 0; i < n; i ++) //注意数组的长度只有n-1
if(i % 2 != numbers[i][0]){ //按顺序必定是最后一位奇偶交替
return i;
}
return n;
}
}
面试题5.8：有个单色屏幕存储在一个一维字节数组中，使得8个连续像素可以存放在一个字节里。屏幕宽度为w，且w可被8整除（即一个字节不会分布在两行上），屏幕高度可由数组长度及屏幕宽度推算出。请实现一个函数drawHorizontalLine(byte[] screen,int width,int x1,int x2,int y)，绘制从点（x1,y）到点（x2,y）的水平线。
package cc150.bit;
public class Render {
public static void main(String[] args) {
// TODO 自动生成的方法存根
int[] a = {0,0,0,0,0,0};
Render rd = new Render();
for(int i=0;i<a.length;i++)
System.out.println(rd.renderPixel(a, 0, 47)[i]);
}
public int[] renderPixel(int[] screen, int x, int y) {
// write code here
for(int i = x; i < y + 1; ++i){
screen[i / 8] |= 1 << (i % 8); //screen中一个元素代表8位，i%8求出每8位中哪一位是1，并左移到相应位置准备合并
}
return screen;
}
}