leetcode 476. 数字的补数（Java版）| How to extract ‘k’ bits from a given position in a number

￡神魔★判官ぃ 2022-10-21 11:47 13阅读 0赞

## 题目 ##

[https://leetcode-cn.com/problems/number-complement/][https_leetcode-cn.com_problems_number-complement]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

--------------------

## 思路 ##

我们想要返回已知数字的补数（num>=1）。

思路：

1.  获取 num 的二进制数
2.  将 num 的二进制数取反
3.  由于取反后，所有高位的 0 都会变为1，所以需要截取有效的低位，得到真正的返回结果

#### \* 参考：How to extract ‘k’ bits from a given position in a number ####

[https://www.geeksforgeeks.org/extract-k-bits-given-position-number/][https_www.geeksforgeeks.org_extract-k-bits-given-position-number]

How to extract ‘k’ bits from a given position ‘p’ in a number?

Examples:

Input : number = 171
                 k = 5 
                 p = 2
    Output : The extracted number is 21
    171 is represented as 0101011 in binary,
    so, you should get only 10101 i.e. 21. （从第2位开始，向左取5位）
    
    Input : number = 72
                k = 5 
                p = 1
    Output : The extracted number is 8
    72 is represented as 1001000 in binary,
    so, you should get only 01000 i.e 8.

1.  Right shift number by p-1.
2.  Do bit wise AND of k set bits with the modified number. We can get k set bits by doing (1 << k) – 1.

**Example:**

// Java program to extract k bits from a given
    // position.
     
    class GFG { 
        // Function to extract k bits from p position
        // and returns the extracted value as integer
        static int bitExtracted(int number, int k, int p)
        { 
            return (((1 << k) - 1) & (number >> (p - 1)));
        }
      
        // Driver code
        public static void main (String[] args) { 
            int number = 171, k = 5, p = 2;
            System.out.println("The extracted number is "+
                   bitExtracted(number, k, p));
        }
    }

**Output:**

The extracted number is 21

--------------------

## 代码 ##

##### 1、易懂版 #####

public class Solution { 
        /** * 给你一个正整数 num ，输出它的补数。补数是对该数的二进制表示取反。 */
        public static int findComplement(int num) { 
            int bitLen = Integer.toBinaryString(num).length();
            return bitExtracted(~num, bitLen, 1);
        }
    
        // Function to extract k bits from p position
        // and returns the extracted value as integer
        static int bitExtracted(int number, int leftIndex, int rightIndex) { 
            System.out.println(Integer.toBinaryString(number));
            int i = ((1 << leftIndex) - 1) & (number >> (rightIndex - 1));
            System.out.println(Integer.toBinaryString(i));
            return i;
        }
    }

##### 2、简化版 #####

class Solution { 
        public int findComplement(int num) { 
            int bitLen=Integer.toBinaryString(num).length();
            return ((1 << bitLen) - 1) & ~num;
        }  
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

[https_leetcode-cn.com_problems_number-complement]: https://leetcode-cn.com/problems/number-complement/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221021/d44dff4ea359401e81c32cec2e0138d5.png
[https_www.geeksforgeeks.org_extract-k-bits-given-position-number]: https://www.geeksforgeeks.org/extract-k-bits-given-position-number/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221021/436b9abbaf4d4bcf89d3fe22ec7be5ad.png