leetcode-1009. 10進数整数の逆符号ブラシノート(c++)

前に書く

難易度:単純

数学の問題、 、 、

テーマの詳細

       N         。  ， 5           "101"，11        "1011"   ，    。  ，  N = 0  ，              。

             1    0     0    1。  ，     "101"         "010"。

         N，                      。

 

   1：

  ：5
  ：2
  ：5         "101"，        "010"，         2 。
   2：

  ：7
  ：0
  ：7         "111"，        "000"，         0 。
   3：

  ：10
  ：5
  ：10         "1010"，        "0101"，         5 。
 

  ：

0 <= N < 10^9
    476：    476：https://leetcode-cn.com/problems/number-complement/   

acコード

問題解決の考え方

N=0、1

を返します.

Nのバイナリはビット毎に反転し、結果は1であり、2^iを結果に積算する.指数は1を加算します(i++,iは初期に0をとります).

説明:バイナリ(101)を1*2^0 + 0*2^1 + 1*2^2 = 5に変換する

class Solution
{
public:
    int bitwiseComplement(int N)
    {
        int i = 0, cc = 0, p = 0;
        if(N == 0)
            return 1;
        while(N)
        {
            cc = !(N&1);
            N = N >> 1;
            if(cc != 0)
                p += pow(2,i);
            i++;
        }
        return p;
    }
};

知識点補足

//    --    
  ：a & 1 == 1
  ：a & 1 == 0

//         2   
//    ( )     1   
n & (n - 1)

//    
//         =     1
- n = ~n + 1 = ~(n - 1)

//         1
n & (-n)
// n & ~(n - 1)

//         1
n & (n - 1)

//   
//     ：         
//    ：        
int add(int a, int b)
{
    int add, jin_wei;
    while (b != 0)                     //         
    {
        add = a^b;
        jin_wei = (a & b) << 1;        //        
        a = add;
        b = jin_wei;
    }
    return add;
}

//   
//          ：a - b = a + (-b) = a + (~b + 1)
int subtract(int a, int b)
{
    return add(a, add(~b, 1));
}

//    ）   [   ]
//   ：        ，             
int multiply(int a, int b)
{
    int ans = 0;
    while (b)
    {
        if (b & 1)
            ans = add(ans, a);
        a = a << 1;
        b = b >> 1;
    }
    return ans;
}

//    [   ]
//          （   ）
int divide(int a, int b)
{
    bool neg = (a > 0)^(b > 0);
    if (a < 0)
        a = -a;
    if (b < 0)
        b = -b;
    if (a < b)
        return 0;

    int zuoyi;
    //zuoyi          
    for (zuoyi = 0; zuoyi < 32; zuoyi++)
    {
        if ((b << zuoyi) >= a)
            break;
    }

    //        
    int shang = 0;
    int i;
    for (i = 0; i < zuoyi; i++)
    {
        if ((b << i) > a)              //      ，    
            continue;
        shang = shang | (1 << i);    //   
        a = a - (b << i);            //    
    }
    if (neg)
        return -shang;
    return shang;
}

//     
int divide(int a, int b)
{
    int count = 0;
    while (a >= b)
    {
        a = substract(a, b);
        count++;
    }
    return count;
}

参考記事

Leetcode——1009.10進数整数の逆符号化——問題解+コード実現

C/C++基礎-原号/逆符号/補符号/ビット操作実現四則演算