二進制補碼0到1,1,0到

我有一個數字，比方說4是二進制表示爲100，我希望實現的是補充數字，即用0替換1和用0替換1。我可以這樣實現它二進制補碼0到1,1,0到

public class Foo { 
    public static void main(String[] args) { 
     String binaryString = Integer.toBinaryString(4); 

     StringBuilder out = new StringBuilder(); 
     char[] chars = binaryString.toCharArray(); 
     char x; 
     for (char ch : chars) { 
      if (ch == '1') { 
       x = '0'; 
      } else { 
       x = '1'; 
      } 
      out.append(x); 
     } 
     System.out.println(Integer.parseInt(out.toString(), 2)); 
    } 
}

在時間複雜性方面達到相同結果的最有效方法是什麼？請注意，輸入可能非常大，我們需要注意整數溢出。

更新否定像〜n這樣的數字會給出錯誤的結果，例如，

System.out.println(~4); 
outputs -5 , expected 3

來源

2014-12-01 sol4me

如何廣泛被認爲是輸入數字？爲什麼'100'去代替'01111'，比如說'11111011'？「10」應該轉到「01」還是轉到「101」？ – user2357112 2014-12-01 18:22:14

另外，如果輸入可能太大而不適合int，那麼你如何接收它們？在stdin上輸入文字？ – user2357112 2014-12-01 18:22:55

那麼使用按位否定（'〜'）怎麼樣？ – fge 2014-12-01 18:22:59

什麼是最有效的方式來實現的時間複雜度同樣的結果？

考慮到int的大小固定爲32，時間複雜度爲O（1）。不過，你的程序效率很低，因爲它創建了一串字符串，字符串解析等等。

如果你跳過乾脆二進制轉換爲此，您可以更快，只需翻轉數，像這樣：

int val = 4; 
int msb = int msb = 32 - Integer.numberOfLeadingZeros(val); 
int inverse = ~val & ((1 << msb)-1); 
System.out.println(inverse);

的~運算符是一元運算符產生的值的二進制補碼。循環計算最高有效位（MSB）的位置。 ((1 << msb)-1)是刪除高於MSB的所有位的掩碼。

Demo.

來源

2014-12-01 18:24:41 dasblinkenlight

注意，這也將翻轉符號位，導致-5而不是3 – 2014-12-01 18:26:17

@WoodrowBarlow，因此將這種操作在相當多的地方存在，難怪這裏 – fge 2014-12-01 18:26:51

@WoodrowBarlow你是對所有其他的編程語言，OP希望一個正數。我添加了代碼來關注原始值的MSB，並根據需要屏蔽結果。謝謝！ – dasblinkenlight 2014-12-01 18:33:43

您可以嘗試使用逐否定：

private int flipBits(int n) { 
    return ~n; 
}

來源

2014-12-01 18:23:10

注意，這也將翻轉符號位，導致-5而不是3 – 2014-12-01 18:26:40

那是我最初的嘗試，但它也將reverte符號位，對於例如的System.out.println（〜4）; // - 5，預計3 – sol4me 2014-12-01 18:27:15

刪除符號位很簡單：只需按位與'整數數量。MAX_VALUE' – fge 2014-12-01 18:29:59

爲什麼不能做這樣的事情：

public static void main(String[] args) { 
     String binaryString = Integer.toBinaryString(4); 
     binaryString = binaryString.replaceAll("1", "-"); 
     binaryString = binaryString.replaceAll("0", "1"); 
     binaryString = binaryString.replaceAll("-", "0");

只有3代碼轉換線...

來源

2014-12-01 18:29:49 brso05

三行代碼=執行了三次正則表達式搜索，比簡單的循環慢得多。 – BackSlash 2014-12-01 18:31:58

@BackSlash +1你打我爲什麼沒有在我原來的職位中使用的replaceAll點，多數民衆贊成 – sol4me 2014-12-01 18:33:50

[這裏]（http://www.browxy.com/SavedCode/24946）這是一個小的演示，如果你想看到不同 – BackSlash 2014-12-01 18:54:10

的BigInteger允許你使用一些任意長度的。找到了否定的方式是找到最大可能值給出了輸入長度和距離。減去輸入值它

//you might want to validate that the string really is a binary number string 
    BigInteger myNum = new BigInteger(inputStr, 2); 
    BigInteger max = new BigInteger("2"); 
    max = max.pow(inputStr.length()).subtract(new BigInteger("1")); 
    BigInteger ans = max.substract(myNum);

來源

2014-12-01 18:39:40 ControlAltDel

二進制補碼0到1,1,0到

回答

相關問題