文档章节

给定一个正整数,找出与其二进制表示中1的个数相同,且大小最接近的那两个数

一贱书生
 一贱书生
发布于 2016/11/19 09:50
字数 2034
阅读 8
收藏 0

/**

 * 功能:给定一个正整数,找出与其二进制表示中1的个数相同,且大小最接近的那两个数。

 * (一个略大一个略小。)

 */

 

三种方法:

方法一:蛮力法

 

方法二:位操作法

[java] view plain copy

 

  1. <span style="white-space:pre">    </span>/** 
  2.      * 方法:位操作法 
  3.      * 思路:获取后一个较大的数 
  4.      *      1)计算c0和c1。c1是拖尾1的个数,c0是紧邻拖尾1的作坊一连串0的个数。 
  5.      *      2)将最右边、非拖尾0变为1,其位置为p=c1+c0。 
  6.      *      3)将位p右边的所有位清零。 
  7.      *      4)在紧邻位置p的右方,插入c1-1个1。 
  8.      * @param n 
  9.      * @return 
  10.      */  
  11.     public static int getNext(int n){  
  12.         int c=n;  
  13.         int c0=0;  
  14.         int c1=0;  
  15.           
  16.         while((c&1)==0&&(c!=0)){  
  17.             c0++;  
  18.             c>>=1;  
  19.         }  
  20.           
  21.         while((c&1)==1){  
  22.             c1++;  
  23.             c>>=1;  
  24.         }  
  25.           
  26.         if(c0+c1==31||c0+c1==0)//c0+c1+1=32,1表示p所在位。  
  27.             return -1;  
  28.           
  29.         int p=c0+c1;//最右边处,非拖尾0的位置。  
  30.         n|=(1<<p);//翻转0为1  
  31.         n&=~((1<<p)-1);//将p右边的所有位清零  
  32.         n|=(1<<(c1-1))-1;//在右边填入(c1-1)个1  
  33.           
  34.         return n;  
  35.     }  
  36.       
  37.     /** 
  38.      * 思路:获取前一个较小的数 
  39.      *      1)计算c0和c1。c1是拖尾1的个数,c0是紧邻拖尾1的作坊一连串0的个数。 
  40.      *      2)将最右边、非拖尾1变为0,其位置为p=c1+c0。 
  41.      *      3)将位p右边的所有位清零。 
  42.      *      4)在紧邻位置p的右方,插入c1+1个1。 
  43.      *      注意:步骤2和3可以合并。 
  44.      * @param n 
  45.      * @return 
  46.      */  
  47.     public static int getPrev(int n){  
  48.         int c=n;  
  49.         int c0=0;  
  50.         int c1=0;  
  51.           
  52.         while((c&1)==1){  
  53.             c1++;  
  54.             c>>=1;  
  55.         }  
  56.           
  57.         if(c==0)  
  58.             return -1;//错误检查!!!全为1时,无法找到  
  59.           
  60.         while((c&1)==0&&(c!=0)){  
  61.             c0++;  
  62.             c>>=1;  
  63.         }  
  64.           
  65.         int p=c0+c1;  
  66.         n&=~((1<<(p+1))-1);//将最右边、非拖尾1变为0,其位置为p=c1+c0;将位p右边的所有位清零。  
  67.         int mask=(1<<(c1+1))-1;//在紧邻(!!!)位置p的右方,插入c1+1个1。  
  68.         n|=mask<<(c0-1);  
  69.           
  70.         return n;  
  71.     }  


方法三:算术法

[java] view plain copy

 

  1. <span style="white-space:pre">    </span>/** 
  2.      * 方法:算术法 
  3.      * 思路:获取后一个较大的数,重新表述问题 
  4.      *      1)计算c0和c1。c1是拖尾1的个数,c0是紧邻拖尾1的作坊一连串0的个数。 
  5.      *      2)将p位置1。 
  6.      *      3)将位p右边的所有位清零。 
  7.      *      4)在紧邻位置p的右方,插入c1-1个1。 
  8.      * 步骤2,3有一种快速做法,将拖尾0置为1(得到p个拖尾1),然后再加1。加1后,所有拖尾1都会翻转,最终位p变为1,后边跟p个0. 
  9.      * @param n 
  10.      * @return 
  11.      */  
  12.     public static int getNextArith(int n){  
  13.         int c=n;  
  14.         int c0=0;  
  15.         int c1=1;  
  16.           
  17.         while((c0&1)==0&&(c!=0)){  
  18.             c0++;  
  19.             c>>=1;  
  20.         }  
  21.           
  22.         while((c1&1)==1){  
  23.             c1++;  
  24.             c>>=1;  
  25.         }  
  26.           
  27.         if(c0+c1==31||c0+c1==0)  
  28.             return -1;  
  29.           
  30.         //将拖尾0置1,得到p个拖尾1  
  31.         n|=(1<<c0)-1;  
  32.         //先将p个1清零,然后位p改为1  
  33.         n+=1;  
  34.         //在右边填入(c1-1)个1  
  35.         n|=(1<<(c1-1))-1;  
  36.           
  37.         return n;  
  38.     }  
  39.     /** 
  40.      * 方法:算术法 
  41.      * 思路:获取前一个较小的数,重新表述问题 
  42.      *      1)计算c0和c1。c1是拖尾1的个数,c0是紧邻拖尾1的作坊一连串0的个数。 
  43.      *      2)将p位清零。 
  44.      *      3)将位p右边的所有位置1。 
  45.      *      4)将位0到位c0-1清零。 
  46.      * @param n 
  47.      * @return 
  48.      */  
  49.     public static int getPrevArith(int n){  
  50.         int c=n;  
  51.         int c0=0;  
  52.         int c1=0;  
  53.           
  54.         while((c&1)==1){  
  55.             c1++;  
  56.             c>>=1;  
  57.         }  
  58.           
  59.         while((c&1)==0&&(c!=0)){  
  60.             c0++;  
  61.             c>>=1;  
  62.         }  
  63.           
  64.         if(c==0)  
  65.             return -1;//错误检查!!!全为1时,无法找到  
  66.           
  67.         n-=(1<<c1)-1;//清除拖尾1,此时p位为1,后面全部为零  
  68.         n-=1;//将p为置0,后面所有位置置1  
  69.         n&=~(1<<(c0-1)-1);//将最后边置c0-1个0  
  70.           
  71.         return n;  
  72.     } 

或者:

1,问题描述

给定一个整数N,该整数的二进制权值定义如下:将该整数N转化成二进制表示法,其中 1 的个数即为它的二进制权值。

比如:十进制数1717 的二进制表示为:0000 0110 1011 0101 故它的二进制权值为7(二进制表示中有7个1)

 

现在要求一个比N大,且最靠近N的数,且这个数的二进制权值与N相同。(这里不考虑Integer.MAX_VALUE 和负数情形。)

对于有符号的32位整数而言:它们的补码如下:

Integer.MAX_VALUE= 0111 1111 1111 1111 1111  1111  1111 1111 (2^32-1)

Integer.MIN_VALUE=  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);
    }
}

 

 

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
ccf-2017-12-1-最小差值

原题: 问题描述 试题分析:最先想到的就是将数存放到数组中,2层循环计算最小差值绝对值即可。(考试的时候智商不在线不知道怎么写的,没有得满分) AC代码: #include include using names...

Big_laoshu
02/02
0
0
面试精选之位操作问题集锦

Java 中位运算符有与(&)、或(|)、非(~)、异或(^)、左移(<<)、右移(>>)、无符号右移(>>>),只针对 int 类型有效,也可以作用于 byte、short、char、long,当为这四种类型时,J...

JohnnyShieh
2017/12/28
0
0
一道C++面试题和补码、无符号数减法运算

面试题在文章第4节。在看面试题之前,可以先看一下1-3节的知识点。 1. 补码 Two's Complement(二补数、补码)是对的数学运算,运算过程为:对二进制序列每一位取反(0->1; 1->0),再加1。 ...

Aspirinrin
2017/11/24
0
0
求二进制中1的个数(编程之美2.1)

行文脉络 解法一——除法 解法二——移位 解法三——高效移位 解法四——查表 扩展问题——异或后转化为该问题 对于一个字节(8bit)的变量,求其二进制“1”的个数。例如6(二进制0000 0110...

技术mix呢
2017/11/09
0
0
面试算法知识梳理(14) - 数字算法

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 面试算法知识梳理(2) - 字符串算法第一部分 面试算法知识梳理(3) - 字符串算法第二部分 面试算法知识梳理(4) - 数组第一部分 面试...

泽毛
2017/12/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

linux 系统的运行级别

运行级别 运行级别 | 含义 0 关机 1 单用户模式,可以想象为windows 的安全模式,主要用于修复系统 2 不完全的命令模式,不含NFS服务 3 完全的命令行模式,就是标准的字符界面 4 系统保留 5 ...

Linux学习笔记
44分钟前
1
0
学习设计模式——命令模式

任何模式的出现,都是为了解决一些特定的场景的耦合问题,以达到对修改封闭,对扩展开放的效果。命令模式也不例外: 命令模式是为了解决命令的请求者和命令的实现者之间的耦合关系。 解决了这...

江左煤郎
52分钟前
2
0
字典树收集(非线程安全,后续做线程安全改进)

将500W个单词放进一个数据结构进行存储,然后进行快速比对,判断一个单词是不是这个500W单词之中的;来了一个单词前缀,给出500w个单词中有多少个单词是该前缀. 1、这个需求首先需要设计好数据结...

算法之名
昨天
10
0
GRASP设计模式

此文参考了这篇博客,建议读者阅读原文。 面向对象(Object-Oriented,OO)是当下软件开发的主流方法。在OO分析与设计中,我们首先从问题领域中抽象出领域模型,在领域模型中以适当的粒度归纳...

克虏伯
昨天
0
0
Coding and Paper Letter(四十)

资源整理。 1 Coding: 1.Tomislav Hengl撰写的非官方作者指南:Michael Gould•Wouter Gerritsma。 UnofficialGuide4Authors 2.R语言包rwrfhydro,社区贡献的工具箱,用于管理,分析和可视化...

胖胖雕
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部