找整数问题

[问答题]

输入：整数A

输出：整数B

条件：A和B的二进制1的个数相同，且A和B之间的距离|A-B|最小。

海阔天空201904231111141


	#include <iostream>



	#include <math.h>



	 



	using namespace std;



	 



	int sameSumOfOne(int a){



	    if(a==0)



	        return 0;



	    int b=0;



	    int pos=0;



	    int bit_num=sizeof(int)*8;



	 



	    if((a&1)==0){



	        while((a&(1<<pos))==0 &&(pos<bit_num))



	            pos++;



	        //cout<<"0_pos="<<pos<<endl;



	 



	        if(po***it_num)



	            return a;



	        if(po***it_num-1)



	            return 1;



	 



	        b=a-(1<<pos)+(1<<(pos-1));



	    }



	    else{



	        while((a&(1<<pos))&&(pos<bit_num))



	            pos++;



	        //cout<<"1_pos="<<pos<<endl;



	        // all bit is 1



	        if(po***it_num)



	            return a;



	        if(po***it_num-1)



	            return -2;



	 



	        b=a-(1<<(pos-1))+(1<<pos);



	    }



	    return b;



	}



	 



	int main()



	{



	    int maximum=(int)((unsigned int)-1 >> 1U);



	    int minimum=(int)~((unsigned int)-1 >> 1U);



	 



	    int a[]={0,1,2,3,4,5,6,7,8,9,10,maximum,minimum,-1,-2};



	    int n=sizeof(a)/sizeof(a[0]);



	    for(int i=0;i<n;i++)



	        cout<<a[i]<<" "<<sameSumOfOne(a[i])<<endl;



	    cout<<endl;



	    return 0;



	}

发表于 2019-05-16 20:20:33 回复(0)

太阳光

javascript:

var num = 1;
var str = parseInt(num).toString(2),n;
n = /10/.test(str) ? str.replace(/^(\d*)10(0*)$/g,function($,b,c,d){return b+"01"+d}):
        str.replace(/^1(1*)$/g,function($,b){return "10"+b});
console.log(parseInt(n,2));

编辑于 2015-06-30 09:31:53 回复(0)

Aut

我的思路是：

①如果A为全1，那么既然A中的1个数和B中1的个数相等，则A == B；

②A为全0，同上；

③假设从低位向高位遍历A，找到最靠近低位的相邻的0和1，交换这两个位上的值即得到B。例：A = 0010 1100 = 44，那么 B = 0010 1010 = 42，|A - B| = 2；

④特殊情况：A = 0111 1111 或者 A = 1000 0000，这时应该将最高位与最低位交换，对应的：B = 1111 1110，B = 0000 0001。此时|A - B|达到最小；

证明：以上只是我的一点想法，暂时不能给出有效的证明，所以代码也没有写，但要实现的话：①②④可以直接判断，③只需用位操作即可实现，所以整个算法比较简单

发表于 2015-06-15 22:27:18 回复(0)

weizier

public class SameNumsOf1{
    public static int getSameNumsOf1(int a){
        if(a==0) return 0;
        int location = 0;
        int b;
        while(((a>>location)&1)==0) location++;
        if(location>0){
            b = a-(1<<location)+(1<<--location);
        }else{
            while(((a>>location)&1)==1) location++;
            b = a+1+(1<<--location)-1;
        }
        return b;
    }
    public static void main(String[] args){
        int[] array = {0,1,2,3,4,5,6,7,8,9,10,11,12};
        for(int num:array){
            System.out.printf("(%d,%d) ",num,getSameNumsOf1(num));
        }
    }

}

发表于 2015-06-15 17:22:24 回复(0)

小菜一枚

int onecount(int n)
{
int zeroposition = 0;
int oneposition = 0;
if(n < 0) n = -n;
if(n ==0 )return 0;
int tmp = n;
int result = 0;
    if((tmp & 1 )== 1)
{
  while((tmp &1) == 1)
  {
   zeroposition++;
   tmp = tmp>>1;
  }
}
else
{
  while((tmp & 1) == 0)
  {
   oneposition++;
   tmp = tmp>>1;
  }
}
if(zeroposition != 0)
    result = n+pow(2,zeroposition) - pow(2,zeroposition-1);
else
  result = n +pow(2,oneposition-1)-pow(2,oneposition);
return result;
}

应该主要是从低位看起，如果最低位为1，那么找出现0的最低位，则结果为2的（0的最低位数）减去2的（0的最低位-1）+n；

如果最低位为0，那么找出现1的最低位，则结果为2的（1的最低位数-1）减去2的（1的最低位）+n；

发表于 2015-06-15 17:13:14 回复(0)

提交观点

问题信息

穷举

上传者：hustacle

难度：

5条回答 1收藏 5648浏览

找整数问题

问题信息

热门推荐

相关试题