5/14-5/20 CareerCup 5.3

Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.

https://github.com/writecoffee/c ... blob/master/5.3.cpp


//////////////////////////////////////////////////////////////////////////////////
// GET_NEXT
//         from the least significant digit find the first bit-1 (pos: i), and then
//        the bit-0 (pos: j), exchange w(j) and w(j-1), finally right shifting the
//        bit-1 to the rightmost positions
//
// GET_PREV
//        similar to GET_NEXT, return the "next smallest number that have the same
//        number of 1 bits in binary expression"
//
// PROOF-OF-NEXT-SMALLEST
// 1.        once we find the 'first bit-0 (pos: j)', and the modified number is
//        2^j - 2^(j-1) bigger than the original one
// 2.        restricted to the rule -- the next largest number have the same number of
//        1 bits in their binary representation, right shifting all the bit-1 to the
//        corner helps remain the "smallest" attribute
// 3.        finally, the result is up to 2^j - 2^(j-1) bigger than the original number
//////////////////////////////////////////////////////////////////////////////////

late post

https://github.com/lyyjohn45/CP_ ... inWithSameOnes.java

https://github.com/285845348/CPP/blob/master/CCP5/CCP5.3.py
似乎我来晚了

也可以先求出整数x中1的个数为n，如果求x的最小值，把最高位设为1，然后最后n-1位为1
如果求x的最大值，从第30位开始，一共n位都设为1

思路和 solution 一样 实现起来差异较大 smallest 6 行 largest 8 行可出解 只测了一般情况的 如有 bug 请指正

1. 
   
2.         public static int __5_3_part1(int n) {
   
3.                 int m = n & (~n << 1);        /* m 最右边的 1 就是 solution 里第一步想找的 1 他是第一个前一位是 0 的 1
   
4.                 int leftOne = m & (~m + 1);   /* 取 m 最右边的 1 */
   
5.                 int rightOnes = ~(n+1) & n;   /* 右边连续的 1 想把它们尽量往左移 如 solution 里的第三步
   
6.                
   
7.                 assert n != rightOnes: "No such number";
   
8.                
   
9.                 /* 下面有三种方式可以找到想把那些 1 左移几位 */
   
10. 
    
11.                 // method 1 纯位运算 借住了求二进制中 1 的个数的经典算法
    
12.                 int cnt = cntOnes( leftOne - ((rightOnes+1)<<1) );
    
13.                 return n ^ leftOne ^ rightOnes | (leftOne>>1) | (rightOnes << cnt);
    
14.                
    
15.                 // method 2 纯数学 猥琐 短
    
16.                 /*int cnt = (int) (Math.log(leftOne/(rightOnes+1)>>1) / Math.log(2) + 1e-6);
    
17.                 return n ^ leftOne ^ rightOnes | (leftOne>>1) | (rightOnes << cnt);*/
    
18.                
    
19.                 // method 3
    
20.                 /*int p = n ^ leftOne ^ rightOnes | (leftOne >> 1);
    
21.                 do {
    
22.                         rightOnes <<= 1;
    
23.                 } while ((p & rightOnes) == 0);
    
24.                 return p | (rightOnes >> 1);*/
    
25.         }
    
26.         
    
27.         public static int __5_3_part2(int n) {
    
28.                 assert ((~n+1) & n) != 0: "No such number";
    
29.                
    
30.                 int p = n & (~n >> 1);
    
31.                 int leftOne = p & (~p + 1);
    
32.                 int q = ~n + 1;
    
33.                 int rightOne = q & (~q + 1);
    
34.                 int condOne = n & (leftOne - rightOne);
    
35.                 int cnt = cntOnes(rightOne-1);
    
36.                 return n ^ leftOne ^ condOne | (leftOne << 1) | (condOne >> cnt);
    
37.         }
    
38.         
    
39.         public static int cntOnes(int n) {
    
40.                 n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
    
41.                 n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    
42.                 n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
    
43.                 n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
    
44.                 n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
    
45.                 return n;
    
46.         }
    

复制代码

我居然用了个排序我确定位置，不厚道。。。
https://github.com/285845348/CPP/blob/master/CCP5/CCP5.3.py