java - 用于补充不包括前导零二进制位的整数值的更好算法

标签 java algorithm bit-manipulation complement

我将首先解释我所说的“补整数值,不包括前导零二进制位”(从现在开始,为简洁起见,我将其称为非前导零位补码或 NLZ-补码)。

例如整数92,二进制数为1011100,如果我们进行普通的按位非或补码,结果为:-93(有符号整数)或111111111111111111111111110100011(二进制)。那是因为前导零位也被补充了。

所以,对于NLZ补码,前导零位不补码,那么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) 的行,或者是否有人可以建议更好的算法?

更新:我也想知道这个非前导零补码的已知术语?

最佳答案

可以通过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

关于java - 用于补充不包括前导零二进制位的整数值的更好算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11827310/

相关文章:

java - REST 服务仅返回当前用户相关的资源

algorithm - 欧拉计划 #388

java - JTextPane - 自动换行插入的 JLabel 组件

java - JRE 选项 java.awt.headless 和 java.awt.headlesslib 之间有什么区别?

c - 在 C 中确定性地生成强力排列

c# - 更新后图像未保存,在 c# 中使用 FileStream 或简单位图

java - 右逻辑/无符号移位插入 1 而不是 0 作为符号位

java - 是否可以使用 JAVA 从文件中读取/写入位?

java - 如何使用 Monkeyrunner API 制作 Java 应用程序?

algorithm - 如何在不使用决策结构的情况下在 python 中将负数更改为零