查找具有相同的權重O（1）

我解決這個問題的最接近的整數：查找具有相同的權重O（1）

那些在整數的二進制表示的計數被稱爲該號碼的重量。以下算法找到具有相同權重的最接近的整數。例如，對於123（0111 1011）2，最接近的整數是125（01111101）2。

O（n）的解決方案，其中n是輸入數字的寬度是通過交換不同的第一對連續位的位置。

有人可以給我一些提示，以解決它在O（1）運行時間和空間？

感謝

來源

2016-07-22 eduardo.leon

書寫十進制或二進制表示本身數量不會爲O （1）。 –

這來自Java編程面試的書籍元素 –

如果number是0或包含二進制的所有1（2^x == number + 1），那麼不能是任何答案。但要檢查即使這不能在O（1）中完成。 – ajayv

正如已經ajayv此評論不能真正在O完成（1）的答案總是取決於位的數量輸入了。然而，如果我們將O（1）解釋爲意味着我們有一個原始整數數據作爲輸入，並且我們對該整數執行的所有邏輯和算術運算都是O（1）（這些比特沒有循環），問題可能會定時解決。當然，如果我們從32位整數改爲64位整數，運行時間會增加，因爲算術運算在硬件上需要更長的時間。

一個可能的解決方案是使用以下功能。第一個給你那裏只有x最低設置位設置

int lowestBitSet(int x){ 
    (x & ~(x-1)) 
}

一批，第二個最低位沒有設置

int lowestBitNotSet(int x){ 
    return ~x & (x+1); 
}

如果你工作在紙上的這幾個例子，你怎麼看他們工作。

現在您可以找到需要使用這兩個函數進行更改的位，然後使用您已經描述的算法。

一個C++實現（不檢查那裏有沒有答案的情況下）

unsigned int closestInt(unsigned int x){ 
    unsigned int ns=lowestBitNotSet(x); 
    unsigned int s=lowestBitSet(x); 
    if (ns>s){ 
    x|=ns; 
    x^=ns>>1; 
    } 
    else{ 
    x^=s; 
    x|=s>>1; 
    } 
    return x; 
}

來源

2016-07-22 11:07:09

static void findClosestIntWithSameWeight(uint x) 
{ 
    uint xWithfirstBitSettoZero = x & (x - 1); 
    uint xWithOnlyfirstbitSet = x & ~(x - 1); 
    uint xWithNextTofirstBitSet = xWithOnlyfirstbitSet >> 1; 

    uint closestWeightNum = xWithfirstBitSettoZero | xWithNextTofirstBitSet; 

    Console.WriteLine("Closet Weight for {0} is {1}", x, closestWeightNum); 

}

來源

2017-08-08 06:41:10 user3512106

嗨，謝謝你的回答！你能編輯它來解釋你的代碼是如何工作的嗎？ – perigon

Java解決方案：

//Swap the two rightmost consecutive bits that are different 
for (int i = 0; i < 64; i++) { 
     if ((((x >> i) & 1)^((x >> (i+1)) & 1)) == 1) { 
      // then swap them or flip their bits 
      int mask = (1 << i) | (1 << i + 1); 
      x = x^mask; 
      System.out.println("x = " + x); 
      return; 
     } 
    }

來源

2018-03-10 18:32:09 user531069

查找具有相同的權重O（1）

回答

相關問題