Лучший алгоритм для дополнения целочисленного значения, исключая начальные нулевые двоичные биты

Сначала я объясню, что я подразумеваю под "дополнением целочисленного значения за исключением двоичных нулевых двоичных разрядов" (отныне я буду называть его "Компонент без начальных нулевых битов" или "NLZ-дополнение" для краткости).

Например, существует целое число 92. Двоичное число равно 1011100. Если мы выполним обычное побитовое-NOT или Complement, результатом будет: -93 (целое число со знаком) или 11111111111111111111111110100011 (двоичное). Это потому, что ведущие нулевые биты тоже дополняются.

Так, для NLZ-дополнения начальные нулевые биты не дополняются, тогда результат NLZ-дополнения 92 или 1011100 будет: 35 или 100011 (двоичный). Операция выполняется путем XOR ввода входного значения с последовательностью в 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), или, если кто-нибудь может предложить лучший алгоритм?

ОБНОВЛЕНИЕ: я также хотел бы знать известный термин этого не ведущего нулевого дополнения?

Источник

2 ответа

Решение

Вы можете получить самый высокий бит через Integer.highestOneBit(i) метод, сдвиньте этот шаг влево, а затем вычтите 1. Это даст вам правильную длину 1s:

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

Например,

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

печать

35
Источник

Очевидно, @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

Источник
Другие вопросы по тегам