在 Java 语言中使用二进制表示整数

Question

这是问题所在：

给你2个

32位数字，N和M，以及两个位位置，i&j。 编写一种方法来设置N中i和j之间的所有位等于M(例如，M在定位i时成为N的子字符串并从 j( 开始(

例如： 输入： int N = 10000000000， M = 10101， i = 2， j = 6; 输出： 整数 N = 10001010100

我的解决方案：

step 1: compose one mask to clear sets from i to j in N 
 mask=   ( ( ( ((1<<(31-j))-1) << (j-i+1) ) + 1 ) << i  ) - 1 
 for the example, we have 
       mask= 11...10000011
step 2: 
      (N & mask) | (M<<i)

问题： 实现算法的便捷数据类型是什么？例如 我们在 C 中有 int n = 0x100000，因此我们可以在 n 上应用按位运算符。 在Java中，我们有BitSet类，它有clear，set方法，但不支持 左/右移运算符;如果我们使用 int，它支持左/右移，但是 没有二进制表示(我不是在谈论二进制字符串表示( 实现这一点的最佳方法是什么？

java代码(阅读所有注释后(：

int x = Integer.parseInt("10000000000",2);
int x = Integer.parseInt("10101",2);
int i = 2, j = 6;
public static int F(int x, int y, int i, int j){
int mask = (-1<<(j+1)) | (-1>>>(32-i));
return (mask & x ) | (y<<i);   
}        

Answer 1

按

位运算符|、&、^和~以及十六进制文字(0x1010(在Java中都可用

。

如果该约束仍然存在，则 32 位数字int s int该约束将是有效的数据类型

顺便说一句，顺便说一下

mask = (-1<<j)|(-1>>>(32-i));

是面具的结构稍微清晰一些

Answer 2

Java的int具有您需要的所有操作。我没有完全理解你的问题(现在太累了(，所以我不会给你一个完整的答案，只是一些提示。(如果需要，我稍后会修改它。

• 以下是连续j个：(1 << j)-1.
• 以下是连续j个，后跟i个零：((1 << j) - 1) << i .
• 这是一个位掩码，它屏蔽了 x 中间的j位置：x & ~(((1 << j) - 1) << i) 。

Integer.toBinaryString()尝试这些以查看结果。(对于负值或太大的值，它们也可能给出奇怪的结果。

Answer 3

我想你误解了Java的工作原理。所有值都表示为引擎盖下的"一系列位"，整数和长整型都包含在其中。

根据您的问题，粗略的解决方案是：

public static int applyBits(int N, int M, int i, int j) {
  M = M << i; // Will truncate left-most bits if too big
  // Assuming j > i
  for(int loopVar = i; loopVar < j; loopVar++) {
    int bitToApply = 1 << loopVar;
    // Set the bit in N to 0
    N = N & ~bitToApply;
    // Apply the bit if M has it set.
    N = (M & bitToApply) | N;
  }
  return N;
}

我的假设是：

• i 是在 N 中设置的最右边(最不重要(位。
• M最右边的位映射到N右起的第i位。
• 过早的优化是万恶之源 - 这就是O(j-i(。如果你像在问题中那样使用了一个复杂的掩码，你可以在 O(1( 中做到这一点，但它不会那么可读，而且可读代码在 97% 的情况下比高效代码更重要。