首页 > 代码库 > 给定一个整数N，找出一个比N大且最接近N，但二进制权值与该整数相同 的数
给定一个整数N，找出一个比N大且最接近N，但二进制权值与该整数相同 的数
1，问题描述
给定一个整数N，该整数的二进制权值定义如下：将该整数N转化成二进制表示法，其中 1 的个数即为它的二进制权值。
比如：十进制数1717 的二进制表示为：0000 0110 1011 0101 故它的二进制权值为7（二进制表示中有7个1）
现在要求一个比N大，且最靠近N的数，且这个数的二进制权值与N相同。(这里不考虑Integer.MAX_VALUE 和负数情形。)
对于有符号的32位整数而言：它们的补码如下：
Integer.MAX_VALUE= http://www.mamicode.com/0111 1111 1111 1111 1111 1111 1111 1111 (2^32-1)
Integer.MIN_VALUE= http://www.mamicode.com/ 1000 0000 0000 0000 0000 0000 0000 0000 （-2^32)
0 = 0000 0000 0000 0000 0000 0000 0000 0000
-1= 1111 1111 1111 1111 1111 1111 1111 1111
（负数的补码是在原码的基础上，符号位不变，其余位取反，末位加1）参考：原码, 反码, 补码 详解
2，问题分析
思路①
先求出N的二进制权值，然后从N+1开始递增，依次判断这个数的二进制权值是否与N相同，直到找到一个相同的二进制权值的数。
而求解二进制权值的算法可以用移位操作来实现。可参考：JAVA中常用的二进制位操作
//求解正数的二进制表示法中的 1 的位数 private static int countBit(int num){ int count = 0; for(; num > 0; count++) { num &= (num - 1); } return count; }
思路①这种方式，当N很大时，效率会很慢。
那有没有更好的思路呢？
其实我们的目的是找到一个数，只要这个数的二进制权值与N相同，且该数大于N且最接近N即可。
那么，可以先将N用二进制表示出来。然后，从低位开始寻找N的二进制中出现 1 之后，第一次出现0的位，假设是第 i 位，那么将第 i 位置为1，得到一个新的数M，此时 M 的二进制中 1 的个数比N多一个。再把M的二进制中的 第 i-1 位的 1 设置为0 ，就得到了大于N且最接近N的二进制权值一样的数。
示例如下：
N= 0010 1001 0101 1111
将第5位置为0，得到了M(最右边的位为第0位)
M= 0010 1001 0111 1111
由于是从低位开始寻找第一次出现0的位。故第5位的右边全是1，再将M的 第 i-1 位(第四位)设置为0，得到了H
H= 0010 1001 0110 1111
H所对应的十进制数，就是题目中要寻找的数。
再比如：
N= 0010 1001 0101 1100
M= 0010 1001 0111 1100
H= 0010 1001 0110 1100
再比如：
N= 0000 1000
M= 0001 1000
H= 0001 0000
3，代码实现：
思路①实现：
import java.util.Scanner;public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNextLong()) { int num = sc.nextInt(); long start = System.currentTimeMillis(); int weight = countBit(num); int k = num + 1; while(countBit(k) != weight) { k++; } long end = System.currentTimeMillis(); System.out.println("res:" + k + " time: " + (end - start)); } sc.close(); } private static int countBit(int num){ int count = 0; for(; num > 0; count++) { num &= (num - 1); } return count; }}
②思路②实现：
import java.util.Scanner;public class Larger_Near_Than_N { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNextInt()) { int number = sc.nextInt(); long start = System.currentTimeMillis(); int result = findNearThanN(number); long end = System.currentTimeMillis(); System.out.println("res:" + result + " time: " + (end - start)); } sc.close(); } private static int findNearThanN(int number){ int result = -1; int first_indexOf_1 = getFirst_1(number); if(first_indexOf_1 != -1)//找到了一个 二进制位 1 { //如果找到了一个二进制位1, indexOf_0不可能为0 int indexOf_0 = getFirst_0(number, first_indexOf_1); int tmp = setBit_1(number, indexOf_0); result = setBit_0(tmp, indexOf_0 - 1); } return result; } //第 i位为1 返回true，为0 返回false private static boolean getBit(int number, int i){ return ((number & (1 << i)) != 0); } //从右到左(低位开始)查找number的二进制位 1 的位置 private static int getFirst_1(int number){ int index = -1; for(int i = 0; i <= 31; i++) if(getBit(number, i)) { index = i; break; } return index;//返回二进制位 1 在 number 中的位置 } //从 start+1 位置开始,查找 number的二进制中,第一个出现的0的位置 private static int getFirst_0(int number, int start){ int index = -1; for(int i = start + 1; i <= 31; i++) { if(!getBit(number, i)) { index = i; break; } } return index; } //将 number 的二进制表示法中的第 i 位设置为 1 private static int setBit_1(int number, int i){ return (number | (1 << i)); } //将 number 的二进制表示法中的第 i 位设置为 0 private static int setBit_0(int number, int i){ int mask = ~(1 << i); return (number & mask); }}
给定一个整数N，找出一个比N大且最接近N，但二进制权值与该整数相同 的数