给定正整数int x,将其用二进制表示,找到和它1的个数相同、且大小最接近的那两个二进制数(一个略大,一个略小)。请返回一个vector,代表这两个数的十进制表示(小的在前)。并保证答案存在。
测试样例:
2
返回:[1,4]
// 就是该数二进制相邻的两个排列 class CloseNumber { public: vector<int> getCloseNumber(int x) { string ans0, ans1, temp; while(x) { temp.push_back(x%2 + '0'); x /= 2; } reverse(temp.begin(), temp.end()); ans0 = temp; ans1 = temp; // 下一个排列 next_permutation(ans1.begin(), ans1.end()); // 上一个排列 prev_permutation(ans0.begin(), ans0.end()); int a[2] = {0}; for(int i = 0; i < ans0.size(); ++i) { a[0] = a[0]*2 + ans0[i]-'0'; } for(int i = 0; i < ans1.size(); ++i) { a[1] = a[1]*2 + ans1[i]-'0'; } return {a[0], a[1]}; } };
根据《程序员面试金典》上的位算数解法写的。 c01是拖尾0的个数,c01是拖尾0左方全为1的位的个数。p位除了拖尾0之外最最右边的0的位,p=c01+c11。x后一个数求取: 1.将位p置1; 2.将位0到p位清零; 3.将位0到c11-1位置1. c1为拖尾1的个数,c0位拖尾1右方全为0的位的个数,p=c0+c1.则x前面一个数的求取步骤: 1.将p位清零。 2.将位p右边所有的位置1. 3.将位0到位c0-1清零。 具体到位上怎么操作,可以翻来数或下电子版来看看。我只是提供途径,公式不好打出来。
#include <vector> classCloseNumber { public: vector<int> getCloseNumber(intx) { // write code here vector <int> result; int c01=0;//拖尾0的个数 int c11=0;//拖尾0左方全为1的个数 int c1=0;//拖尾1的个数 int c0=0;//拖尾1左方全为0的位个数 int c = x,d=x;//临时变量 //分别求取 while(((c & 1) == 0) && (c!=0)){ c01 ++; c >>= 1; } while((c & 1)==1){ c11 ++; c >>= 1; } while((d & 1)==1){ c1 ++; d >>= 1; } while(((d & 1) == 0) && (d!=0)){ c0 ++; d >>= 1; } result.push_back((x - (1<<(c1))-(1<<(c0-1)) +1)); result.push_back((x + (1<<(c11-1)) + (1<<c01) -1)); return result; } };
import java.util.*; /* * 思路:1、getNum得到一个数中1的个数 * 2、向后搜索略小的一个arr[0] * 3、向前搜索略大的一个arr[1] */ public class CloseNumber { public int getNum(int n){ int count = 0; while(n != 0){ if((n&1) == 1){ count++; } n = n>>1; } return count; } public int[] getCloseNumber(int x) { // write code here int[] arr = new int[2]; int num = getNum(x); int i; for(i = x-1; getNum(i) != num; i--); arr[0] = i; for(i = x+1; getNum(i) != num; i++); arr[1] = i; return arr; } }
class CloseNumber { public: vector<int> getCloseNumber(int x) { vector<int> res; if(x<=0) return res; int prev=x+1,next=x-1,num=getonenum(x); while(getonenum(next)!=num){ --next; } res.push_back(next); while(getonenum(prev)!=num){ ++prev; } res.push_back(prev); return res; } private: int getonenum(int data){ int n=0; while(data){ ++n; data=data&(data-1); } return n; } };我还是****法,通过位操作未必真能节省指令,待有空做实验比较。
import java.util.*; public class CloseNumber { public int[] getCloseNumber(int x) { int min=x-1,max=x+1; while(Integer.bitCount(x)!=Integer.bitCount(min)&&min>=0){ min--; } while(Integer.bitCount(x)!=Integer.bitCount(max)){ max++; } int arr[]={min,max}; return arr; } } 程序员面试金典java http://blog.csdn.net/sinat_22797429/article/details/75451808
# -*- coding:utf-8 -*- class CloseNumber: def getCloseNumber(self, x): res = [0, 0] n = x while True: n -= 1 if bin(x).count("1") == bin(n).count("1"): res[0] = n break n = x while True: n += 1 if bin(x).count("1") == bin(n).count("1"): res[1] = n break return res
# -*- coding:utf-8 -*- class CloseNumber: def getCloseNumber(self, x): return self.getPrev(x), self.getNext(x) def getNext(self, n): c = n c0 = 0 c1 = 0 while c & 1 == 0 and c: c0 += 1 c >>= 1 while c & 1 == 1: c1 += 1 c >>= 1 if c0 + c1 >= 31 or c0 + c1 == 0: return False p = c0 + c1 # 翻转最右边非拖尾0 n |= (1 << p) # 将p右方的所有为清零 n &= ~((1 << p) - 1) # 在右方插入(c1 - 1)个1 n |= (1 << (c1 - 1)) - 1 return n def getPrev(self, n): c = n c0 = 0 c1 = 0 while c & 1 == 1: c1 += 1 c >>= 1 if c == 0: return -1 while c & 1 == 0 and c: c0 += 1 c >>= 1 p = c0 + c1 # 位0到p位清零 n &= (~0) << (p + 1) # 在p后面插入c1 + 1个1 n |= ((1 << (c1 + 1)) - 1) << (c0 - 1) return n
class CloseNumber { public: vector<int> getCloseNumber(int x) { vector<int> res; int pos10 = find10(x); int pos01 = find01(x); // get small one int s = (x&(~0)<<pos10+1) + (1<<(pos10-1)); int mask = (1<<(pos10-1)) - 1; int n = x&mask; int cnt_one = count_one(n); if (cnt_one > 0) { n = ((1<<cnt_one) - 1)<<(pos10-1-cnt_one); s += n; } res.emplace_back(s); // get larger one int l = (x&(~0)<<pos01+1) + (1<<pos01); mask = (1<<(pos01-1)) - 1; n = x&mask; cnt_one = count_one(n); if (cnt_one > 0) { n = (1<<cnt_one) - 1; l += n; } res.emplace_back(l); return res; } int count_one(int n) { int cnt = 0; while (n) { if ((n&1) == 1) ++cnt; n >>= 1; } return cnt; } int find01(int n) { int pos = 0; while (n && (n&1) == 0) { ++pos; n >>= 1; } while (n && (n&1) == 1) { ++pos; n >>= 1; } if (n == 0) return -1; return pos; } int find10(int n) { int pos = 0; while (n && (n&1) == 1) { ++pos; n >>= 1; } if (n == 0) return -1; while (n && (n&1) == 0) { ++pos; n >>= 1; } return pos; } };
比较直观的一种做法:
大的数:找到右侧第一个‘01’对,然后互换,然后将右侧所有的0放在最左边,所有的1放在最右边
小的数:找到右侧第一个'10'对,然后互换,然后将右侧所有的1放在最左边,所有的0放在最右边
class CloseNumber { public: vector<int> getCloseNumber(int x) { // write code here int small=x; string s; int left10=-1; // "10"中0的位置 int right01=-1; // "01"中1的位置 int bitcnt=0; while(small!=0){ if(small&1){ s='1'+s; }else{ s='0'+s; } small/=2; bitcnt++; } for(int i=s.size()-1;i>0;--i){ if( right01==-1 && s[i]=='1' && s[i-1]=='0'){ right01=s.size()-1-i; } if( left10==-1 && s[i]=='0' && s[i-1]=='1'){ left10=s.size()-1-i; } } vector<int> ret(2,x); if(right01==-1){ ret[1]=x<<1; }else{ ret[1]=x+(1<<right01); for(int i=right01-1,j=0;j<i;++j,--i){ while(i>0 && s[s.size()-1-i]=='0') --i; while(j<s.size() && s[s.size()-1-j]=='1') ++j; if(j<i){ ret[1]=ret[1]-(1<<i)+(1<<j); } } } ret[0]=x-(1<<left10); for(int i=left10-1,j=0;j<i;++j,--i){ while(i>0 && s[s.size()-1-i]=='1') --i; while(j<s.size() && s[s.size()-1-j]=='0') ++j; if(j<i) { ret[0]=ret[0]+(1<<i)-(1<<j); } } return ret; } };
class CloseNumber { public: int F(int n){ int s = 1; while(n){ s += n&1; n>>=1; } return s; } vector<int> getCloseNumber(int x) { vector<int> r; int cnt = F(x),i; for(i=x-1;F(i)!=cnt && i>0;i--); r.push_back(i); for(i=x+1;F(i)!=cnt;i++); r.push_back(i); return r; } };
import java.util.*; public class CloseNumber { public int[] getCloseNumber(int x) { // write code here int[] a=new int[2]; int left=x-1; int right=x+1; int num=oneNum(x); while(left>0){ if(num==oneNum(left)) break; left--; } while(true){ if(num==oneNum(right)) break; right++; } a[0]=left; a[1]=right; return a; } public int oneNum(int x){ int count=0; while(x!=0){ if((x&1)==1) count++; x>>=1; } return count; } }
public static int[] getCloseNumber(int x) { // write code here String xBin = Integer.toBinaryString(x); int oneNumber = 0; for (int i = 0; i < xBin.length(); i++) { if (xBin.charAt(i) == '1') { oneNumber++; } } int[] result = new int[2]; for (int i = x-1; i > 0; i--) { String xxBin = Integer.toBinaryString(i); int onexNumber = 0; for (int k = 0; k < xxBin.length(); k++) { if (xxBin.charAt(k) == '1') { onexNumber++; } } if (onexNumber == oneNumber) { result[0] = i; break; } } for (int j = x+1; j < Integer.MAX_VALUE; j++) { String xxBin = Integer.toBinaryString(j); int onexNumber = 0; for (int k = 0; k < xxBin.length(); k++) { if (xxBin.charAt(k) == '1') { onexNumber++; } } if (onexNumber == oneNumber) { result[1] = j; break; } } return result;
} 笨笨的方法
public class CloseNumber { public int[] getCloseNumber(int x) { int n, c0, c1; int[] result = new int[2]; for (n = x, c1 = 0; (n & 1) == 1; n >>= 1, ++c1); for (c0 = 0; (n & 1) == 0; n >>= 1, ++c0); result[0] = x - (1 << c1) - (1 << (c0 - 1)) + 1; for (n = x, c0 = 0; (n & 1) == 0; n >>= 1, ++c0); for (c1 = 0; (n & 1) == 1; n >>= 1, ++c1); result[1] = x + (1 << c0) + (1 << (c1 - 1)) - 1; return result; } }
class CloseNumber { public: int getNext(int n){ //compute c0,c1 int c=n; int c0=0; int c1=0; while(((c&1)==0)&&(c!=0)){ c0++; c>>=1; } while((c&1)==1){ c1++; c>>=1; } if(c1+c1==31||c0+c1==0){ return -1; } int p=c1+c0; n|=(1<<p); n&=~((1<<p)-1); n|=(1<<(c1-1))-1; return n; } int getPrev(int n){ int temp=n; int c0=0; int c1=0; while(temp&1==1){ c1++; temp>>=1; } if(temp==0) return -1; while(((temp&1)==0)&&(temp!=0)){ c0++; temp>>=1; } int p=c0+c1; n&=((~0)<<(p+1)); int mask=(1<<(c1+1))-1; n|=mask<<(c0-1); return n; } vector<int> getCloseNumber(int x) { // write code here int next=getNext(x); int pre=getPrev(x); vector<int> result; result.push_back(pre); result.push_back(next); return result; } };
public int[] getCloseNumber(int x) { int[] a = new int[2]; getNext(x, a); getPrev(x, a); return a; } void getPrev(int x, int[] a) { int k = x, p = 0, c0 = 0; // c0代表0的个数 // 求拖尾1(1后面跟0)的位置p for (; k != 0; k >>= 1, p++) { if ((k & 1) == 0) c0++; else if (c0 > 0) break; } // 将p位置0 k = 1 << p; x &= ~k; // 将p后所有位置0 x &= ~(k - 1); // 补全c0-1个0放在最后,其它为1 x |= (k - 1) & ~((1 << (c0 - 1)) - 1); a[0] = x; } void getNext(int x, int[] a) { int k = x, p = 0, c1 = 0; // c1代表1的个数 // 求不拖尾0(0后面跟1)的位置p for (; k != 0; k >>= 1, p++) { if ((k & 1) == 1) c1++; else if (c1 > 0) break; } // 将p位置1 k = 1 << p; x |= k; // 将p后所有位置0 x &= ~(k - 1); // 补全c1-1个1 x |= (1 << c1 - 1) - 1; a[1] = x; }
import java.util.*; public class CloseNumber { public int[] getCloseNumber(int x) { // write code here int[] res=new int[2]; int num=getOneNum(x); int left=x-1; int right=x+1; while(left>0){ if(num==getOneNum(left)) break; left--; } while(true){ if(num==getOneNum(right)) break; right++; } res[0]=left; res[1]=right; return res; } public int getOneNum(int x){ int count=0; while(x!=0){ if((x & 1)==1){ count++; } x>>=1; } return count; } }
vector<int> getCloseNumber(int x) { // write code here vector<int> out; out.push_back(findLe(x)); out.push_back(findGe(x)); return out; } int findGe(int n){ unsigned t1 = n&(-n); unsigned t2 = n + t1; return t2 | ((n^t2) / t1) >> 2; } int findLe(int n){ unsigned t1 = (n + 1)&(~n);//最右边的0位置 ; if (t1 > 0){ int t2 = n / t1*t1;//n最右边0右边的1置为0; unsigned t3 = t2&(-t2); //t2最右边的1 unsigned t4 = t3 / (t1<<1); unsigned t5 = t2^t3; return t5 | ((t3 - 1) / t4*t4); } else{ unsigned t1 = n&(-n);//n最右边的1 return n ^ ((t1 >> 1) | t1); } } };
class CloseNumber { public: vector<int> getCloseNumber(int x) { vector<int> res; int count=getonecount(x); int lower=x-1; int larger=x+1; while(getonecount(lower)!=count)lower--; res.push_back(lower); while(getonecount(larger)!=count)larger++; res.push_back(larger); return res; } int getonecount(int x) { int count=0; for(;x;count++) x=x&(x-1); return count; } };