|
| 1 | +#!/usr/bin/python3 |
| 2 | +""" |
| 3 | +Every non-negative integer N has a binary representation. For example, 5 can be |
| 4 | +represented as "101" in binary, 11 as "1011" in binary, and so on. Note that |
| 5 | +except for N = 0, there are no leading zeroes in any binary representation. |
| 6 | +
|
| 7 | +The complement of a binary representation is the number in binary you get when |
| 8 | +changing every 1 to a 0 and 0 to a 1. For example, the complement of "101" in |
| 9 | +binary is "010" in binary. |
| 10 | +
|
| 11 | +For a given number N in base-10, return the complement of it's binary |
| 12 | +representation as a base-10 integer. |
| 13 | +
|
| 14 | +Example 1: |
| 15 | +Input: 5 |
| 16 | +Output: 2 |
| 17 | +Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 |
| 18 | +in base-10. |
| 19 | +
|
| 20 | +Example 2: |
| 21 | +Input: 7 |
| 22 | +Output: 0 |
| 23 | +Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 |
| 24 | +in base-10. |
| 25 | +
|
| 26 | +Example 3: |
| 27 | +Input: 10 |
| 28 | +Output: 5 |
| 29 | +Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is |
| 30 | +5 in base-10. |
| 31 | +
|
| 32 | +Note: |
| 33 | +0 <= N < 10^9 |
| 34 | +""" |
| 35 | + |
| 36 | + |
| 37 | +classSolution: |
| 38 | +defbitwiseComplement(self,N:int)->int: |
| 39 | +""" |
| 40 | + invert the bit, and the mask it |
| 41 | + """ |
| 42 | +mask=1 |
| 43 | +cur=N |
| 44 | +whilecur>>1: |
| 45 | +cur>>=1 |
| 46 | +mask<<=1 |
| 47 | +mask+=1 |
| 48 | + |
| 49 | +return~N&mask |