補全整數值不包括前導零二進制位的更好算法

我將首先解釋「補全整數值，不包括前導零二進制位」（從現在開始，我將稱之爲無引導零位補碼或NLZ - 爲了簡潔起見）。

例如，存在整數92.二進制數爲1011100.如果我們執行正常的按位NOT或Complement，則結果爲：-93（有符號整數）或11111111111111111111111110100011（二進制）。這是因爲前導零位也被補充。因此，對於NLZ-Complement，前導零位不是互補的，那麼92或1011100的NLZ補碼結果是：35或100011（二進制）。操作是通過將輸入值與1位序列異或爲非前導零值來執行的。插圖：

補全整數值不包括前導零二進制位的更好算法

92: 1011100 
    1111111 (xor) 
    -------- 
    0100011 => 35

我所作的java的算法是這樣的：

public static int nonLeadingZeroComplement(int n) { 
    if (n == 0) { 
     return ~n; 
    } 
    if (n == 1) { 
     return 0; 
    } 

    //This line is to find how much the non-leading zero (NLZ) bits count. 
    //This operation is same like: ceil(log2(n)) 
    int binaryBitsCount = Integer.SIZE - Integer.numberOfLeadingZeros(n - 1); 

    //We use the NLZ bits count to generate sequence of 1 bits as much as the NLZ bits count as complementer 
    //by using shift left trick that equivalent to: 2 raised to power of binaryBitsCount. 
    //1L is one value with Long literal that used here because there is possibility binaryBitsCount is 32 
    //(if the input is -1 for example), thus it will produce 2^32 result whom value can't be contained in 
    //java signed int type. 
    int oneBitsSequence = (int)((1L << binaryBitsCount) - 1); 

    //XORing the input value with the sequence of 1 bits 
    return n^oneBitsSequence; 
}

我需要一個建議如何優化上述算法，尤其是線，用於產生1個比特序列補充程序（oneBitsSequence），還是有人可以提出更好的算法？

更新：我也想知道這個非領先的零補碼的已知術語？

來源

2012-08-06 null

所以對於要返回0兩種一切權力因此，從0開始的順序是1，0，0， 0，0，2，1，0，0，6，...這有什麼用？ – 2012-08-06 11:30:36

你稱之爲「NLZ-Complement」就是所謂的Ones的補充。 http://en.wikipedia.org/wiki/One%27s_compliment – 2012-08-06 11:53:32

@MisterSmith：你確定嗎？我認爲不是。補碼也補充了前導零。 – null 2012-08-06 11:57:54

你可以通過Integer.highestOneBit(i)方法最高的國家之一位，移位這一步了，再減去1。這讓你的1 S上的正確長度：

private static int nonLeadingZeroComplement(int i) { 
    int ones = (Integer.highestOneBit(i) << 1) - 1; 
    return i^ones; 
}

例如，

System.out.println(nonLeadingZeroComplement(92));

打印

來源

2012-08-06 11:27:58 Keppil

我知道了！必須有一個內置的功能，可以使這個更簡單。哈哈，你讓這很容易。你知道這個NLZ補充的真正/已知的術語嗎？ – null 2012-08-06 11:59:48

@suud：不，對不起，我不知道這個專門的術語。 – Keppil 2012-08-06 12:11:20

明顯@keppil具有省找到最短的解決方案。另一種解決方案可能是。

private static int integerComplement(int n){ 

    String binaryString = Integer.toBinaryString(n); 

    String temp = ""; 
    for(char c: binaryString.toCharArray()){ 
     if(c == '1'){ 
      temp += "0"; 
     } 
     else{ 
      temp += "1"; 
     } 
    } 
    int base = 2; 
    int complement = Integer.parseInt(temp, base); 

    return complement; 
}

例如，

System.out.println(nonLeadingZeroComplement(92));

打印回答，因爲35

來源

2014-09-10 15:45:24 shrishinde

補全整數值不包括前導零二進制位的更好算法

回答

相關問題