解方程: x+y=x|y

本文内容遵从CC版权协议 转载请注明出自:   http://blog.csdn.net/masterluo

        给定两个正整数x, k,求第k个最小的正整数y,满足y满足x+y = x|y.   x (1≤x≤2 000 000 000),   k(1≤k≤2 000 000 000)  

 

        将x,y用二进制表示,len[x], len[y]分别表示需要多少位二进制位表示x, y. x_i表示x的二进制的低i位(从0开始).

        (1):如果len[y]>len[x], 且y的低len[x]位全为0,这样的y都是满足x+y = x|y的。如x=11，则len[x]=4.

        0000 1011
        xxxx 0000
        -----------
        xxxx 1011

        (2):y≤x时有多少个这样的满足x+y = x|y 呢？

        设x=x_n-1x_n-2……x₀,存在y≤x满足x+y = x|y.如果x_i( 0≤i＜n)如果x_i＝0,则y_i可以是0/1, 如果x_i=1,则y_i=0.故x=x_n-1x_n-2……x₀时存在2^k(k为x二进制位中0的个数)个y(y≤x),使其满足x+y = x|y.

        (3):y≤x时不存在除(2)外的其它y满足方程x+y = x|y．由二可知当y≤x时要满足方程x+y = x|y，即在x+y的任何一位都不能产生进位．用反证法证明．设最低一次进位是在第i位．由于第i位发生了进位且为第一次进位，则一定x_i=1, y_i=1. carry_i-1=0(carry_i表示第i位的进位值). 此时x+y结果为z, z_i=(x_i+y_i)%2=0. x|y的结果为w. w_i=(x_i|y_i)=1. z_i != w_i.故第i位不可能产生进位，得证。

        由上面分析可以得到一个很简单的求解方法：第k小的y就是将x扩展(高位补0),从低位向高位填充k的二进制位。如果x_i=0，填充一位k的二进制位。如果x_i=1, 则y_i=0.直至将所有的k的二进制全部填充即可。

 

1. #include <string>
2. #include <iostream>
3. using namespace std;
4.  
5. class BitwiseEquations {
6. public:
7.     long long kthPlusOrSolution ( int, int );
8.     string getBin ( int );
9.  
10. };
11.  
12. /*
13. *返回x的二进制形式的字符串
14. */
15.  
16. string BitwiseEquations:: getBin ( int x ) {
17.     string ret= "";
18.     if (x== 0 ) {
19.         ret= "0";
20.         return ret;
21.     }
22.     while (x> 0 ) {
23.         ret= char (x% 2+ '0' )+ret;
24.         x/= 2;
25.     }
26.     return ret;
27. }
28.  
29. /*
30. *求第k小的y 满足x+y = x|y
31. */
32. long long BitwiseEquations:: kthPlusOrSolution ( int x, int k ) {
33.     string strx, strk;
34.     strx=getBin (x );
35.     strk=getBin (k );
36.     int lx=strx. length ( ) -1;
37.     int lk=strk. length ( ) -1;
38.  
39.     string ret= "";
40.     //填充k的二进制位
41.     while (lx>= 0 && lk>= 0 ) {
42.         if (strx [lx ]== '1' ) {
43.             ret= "0"+ret;
44.             --lx;
45.         } else {
46.             ret=strk [lk ]+ret;
47.             --lx;
48.             --lk;
49.         }
50.     }
51.     //高位补0填充k的二进制位
52.     while (lk>= 0 ) {
53.         ret=strk [lk-- ]+ret;
54.     }
55.  
56.     long long rets= 0;
57.     for ( int i= 0; i<ret. length ( ); ++i ) {
58.         rets= (rets<< 1 )+ret [i ]- '0';
59.     }
60.     return rets;
61. }