Better algorithm for complementing integer value excluding the leading zero binary bits

Question

I will explain first what I mean by "complementing integer value excluding the leading zero binary bits" (from now on, I will call it Non Leading Zero Bits complement or NLZ-Complement for brevity).

For example, there is integer number 92. the binary number is 1011100. If we perform normal bitwise-NOT or Complement, the result is: -93 (signed integer) or 11111111111111111111111110100011 (binary). That's because the leading zero bits are being complemented too.

So, for NLZ-Complement, the leading zero bits are not complemented, then the result of NLZ-complementing of 92 or 1011100 is: 35 or 100011 (binary). The operation is performed by XORing the input value with sequence of 1 bits as much as the non-leading zero value. The illustration:

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

I had made the java algorithm like this:

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;
}

I need an advice how to optimize above algorithm, especially the line for generating sequence of 1 bits complementer (oneBitsSequence), or if anyone can suggest better algorithm?

UPDATE: I also would like to know the known term of this non-leading zero complement?

Answer 1

You can get the highest one bit through the Integer.highestOneBit(i) method, shift this one step left, and then subtract 1. This gets you the correct length of 1s:

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

For example,

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

prints

35

Answer 2

obviously @keppil has provided shortest solution. Another solution could be like.

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;
}

For example,

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

Prints answer as 35