補碼Leetcode解決方案


難度級別 容易獎學金
經常問 蘋果
位操作 Cloudera的

問題陳述

在這個問題上,我們得到一個十進制數。 目的是找到它 補充.

N = 15
0
N = 5
2

補碼Leetcode解決方案

接近(一點一點翻轉)

我們可以翻轉每一個 在整數“ N”中獲取其補碼。 重要的是,我們 不能 翻轉所有的32位。 因為這將導致其二進制1的補碼。 我們只需要從LSB開始翻轉到數字中最左邊的設置位。 我們可以通過將給定數字N除以2直至變為零來實現這一點。 並且在每次迭代中,我們可以翻轉相應的位。

補碼Leetcode解決方案的實現

C ++程序

#include <bits/stdc++.h>

using namespace std;

int findComplement(int num) {
    int todo = num , i = 0;
    while(todo > 0) {
        num ^= (1 << i);
        todo >>= 1;
        ++i;
    }
    return num;
}

int main() {
    int n = 15;
    cout << findComplement(n) << endl;
    return 0;
}

Java程序

class number_complement {
    public static void main(String args[]) {
        int n = 15;
        System.out.println(findComplement(n));
    }

    public static int findComplement(int num) {
        int todo = num , i = 0;
        while(todo > 0) {
            num ^= (1 << i);
            todo >>= 1;
            ++i;
        }
        return num;
    }
}
0

補碼Leetcode解決方案的複雜性分析

時間複雜度

O(log2N),其中N =給定的整數。 我們迭代給定數字中的位數。

空間複雜度 

O(1),因為我們只使用常量內存。

方法(優化)

優化的方法是不使用任何 分枝 在代碼中。 也就是說,要在沒有任何循環或基本上沒有任何分支指令的情況下解決代碼。 在這種方法中,我們首先找到一個具有以下特徵的二進制掩碼: 所有位設置,從 '0th'位最左邊的設定位 給定數字,然後將其與自身進行XOR。 這將為我們提供所需的補充。

為了找到N所需的二進制掩碼,我們將給定的數字與N >> 1,N >> 2,N >> 4,…N >> 16按位或,其中N >> k =將N右移k的地方。 通過這種方法,我們將設置最高有效位(最左邊的位)之後的所有位,並產生所需的掩碼。

補碼Leetcode解決方案的實現

C ++程序

#include <bits/stdc++.h>

using namespace std;

int findComplement(int num) {
    int mask = num;
    mask |= mask >> 1;
    mask |= mask >> 2;
    mask |= mask >> 4;
    mask |= mask >> 8;
    mask |= mask >> 16;
    return num ^ mask;
}

int main() {
    int n = 15;
    cout << findComplement(n) << endl;
    return 0;
}

Java程序

class number_complement {
    public static void main(String args[]) {
        int n = 15;
        System.out.println(findComplement(n));
    }

    public static int findComplement(int num) {
        int mask = num;
        mask |= mask >> 1;
        mask |= mask >> 2;
        mask |= mask >> 4;
        mask |= mask >> 8;
        mask |= mask >> 16;
        return num ^ mask;
    }
}
0

補碼Leetcode解決方案的複雜性分析

時間複雜度

O(1),因為按位二進制運算非常快,儘管這些運算需要 O(log2N),時間複雜度對於32位整數是恆定的。

空間複雜度 

O(1),因為我們只使用恆定的內存空間。