C：在O中設置整數的第i位爲1（1）

現在，我知道設置數字的第i位的方法是使用移位運算符來移位1，直到達到所需位，然後只是或它與數字。但是這個過程是O（數字的長度），因爲把一個數字移到第i個位置就像遍歷到那裏，對嗎？如果我錯了，請糾正我。C：在O中設置整數的第i位爲1（1）

這裏是我的代碼：

x = x| (1<<i)

有沒有辦法在O（1）要做到這一點？換句話說，如何直接訪問數字中的位？我在考慮數組索引的問題。

來源

2017-02-23 Tinkidinki

我認爲你錯了。這個操作是O（1）。 –

這取決於您的硬件，即CPU。顯示您的代碼和**相關**機器代碼。但是您可以使用查找表來安全地（但可能更慢）。 – Olaf

這個操作O（1）如何？它將不得不遍歷數字，對吧？ – Tinkidinki

轉移1通過k位在硬件完成。在一個非常簡化的級別中，一個n位CPU具有n寄存器，它們表示在每個方向上移位了0,1,2，...，n-1位的數字。執行移位操作時，CPU根據移位次數將數字加載到寄存器k中，並在下一個週期中讀取輸出。這使得移位O（1）操作。

This Q&A有一個圖解釋了使用多路複用器的現代CPU的O（1）「魔術」背後的硬件。

來源

2017-02-23 13:39:09 dasblinkenlight

謝謝！！！但從圖中，我推斷，對於2^i位系統，我需要電路層，對吧？所以對於一個給定的系統來說，在不變的時間內完成移位 – Tinkidinki

@Tinkidinki是的，桶式移位器需要用於2^i位系統的'i'層。然而，所有'i'層同時處於活動狀態，所以儘管我們談論的是門延遲，但操作在一個週期內完成（當然，這比門延遲要長得多）。 – dasblinkenlight

不是所有的處理器都有桶式移位器...... P4沒有。 –

正如其他人指出的，n |= 1 << i是而不是 O（n）。這是因爲在大多數CPU中的位移操作是單指令，在我需要一個或兩個IIRC的那一刻我就很熟悉。

但是，如果您將引入C代碼內的循環，那麼這當然會爲O（n），如：

n = 1; 
for(j = 0; j < i; ++j) 
    n <<= 1; 
x |= n;

對於重構位設置在一般設置位一個整數值，你可以這樣做：

typedef enum x_bits_e { 
    x_bit1 = 1 << 0; 
    x_bit2 = 1 << 1; 
    x_bit3 = 1 << 2; 
    // and so on 
}; 

int16_t set_bit_in_x(int16 x, x_bits_e i) 
{ 
    return x | i; 
}

來源

2017-02-23 13:36:20 Toby

反對的任何理由？ – Toby

沒問題。我可以回答你的答案:) –

我沒有，但你可以改進命名 – ttdado

C：在O中設置整數的第i位爲1（1）

回答

相關問題