本章涵盖了位操作的最重要方面，当它构成技术面试的一部分时，您应该了解这些方面。这样的问题在面试中经常遇到，也不容易。人类的思维不是为了操纵比特而设计的。计算机就是为此而设计的。这意味着操作位非常困难并且极易出错。因此，建议始终仔细检查每个位操作。

对于掌握这类问题，有两件事非常重要，如下所示：

• 您必须非常了解位理论（例如，位运算符）
• 你必须尽可能多地练习位操作

在处理以下主题时，我们需要牢记这两个陈述：

• 了解位操作
• 编码挑战

让我们从理论部分开始。强烈建议您从本节中提取图表。在本章的第二部分，他们将成为你最好的朋友。

本章中的所有代码都可以在 GitHub 上找到 https://github.com/PacktPublishing/The-Complete-Coding-Interview-Guide-in-Java/tree/master/Chapter09。

在 Java 中，我们可以操作以下数据类型的 位：byte（8 位）、short（16 位）、int（32 位）、long（64 位） , 和 char（16 位）。

例如，让我们使用正数 51。在这种情况下，我们有以下语句：

• 51的二进制表示是110011。
• 因为 51 是 int，所以表示为 32 位值；即 1 或 0 的 32 个值（从 0 到 31）。
• 110011 左边的所有位置实际上都用零填充，总共最多 32 位。
• 这意味着 51 是 00000000 00000000 00000000 00110011（我们将其呈现为 110011，因为 显示二进制表示通常不需要额外的零）。

Obtaining the binary representation of a Java integer

我们怎么知道 110011 是 51 的二进制表示？我们如何计算 112 或任何其他 Java 整数的二进制表示？一种简单的方法包括连续将数字除以 2，直到 商小于 1，然后将余数解释为 0 或 1。0 的余数被解释为 0，而大于 0 的余数被解释为 1。例如，让我们将此应用于 51：

1. 51/2 = 25.5 的商为 25，余数为 5 ->商店 1
2. 25/2 = 12.5 的商为 12，余数为 5 ->商店 1
3. 12/2 = 6 的商为 6，余数为 0 ->商店 0
4. 6/2 = 3 的商为 3，余数为 0 ->商店 0
5. 3/2 = 1.5 的商为 1，余数为 5 ->;商店 1
6. 1/2 = 0.5 的商为 0，余数为 5 ->;商店 1

因此，我们存储了 110011，它是 51 的二进制表示。其余 26 位是零（00000000 00000000 00000000 00110011）。逆过程从右到左开始，包括添加 2 的幂，其中位数等于 1。所以这里，51 = 20+21+24+25。下图可以帮助我们理解这一点：

图 9.1 – 二进制到十进制（32 位整数）

在 Java 中，我们可以通过 Integer#toString(int i, int radix) 或 Integer#toBinaryString(int i) 。例如，基数 2 表示二进制：

// 110011
System.out.println("Binary: " + Integer.toString(51, 2));
System.out.println("Binary: " + Integer.toBinaryString(51));

逆过程（从二进制到十进制）可以通过Integer#parseInt(String nr, int radix)得到：

System.out.println("Decimal: " 
  + Integer.parseInt("110011", 2));  //51

接下来，让我们处理按位 运算符。这些运算符允许我们 操作位，因此了解它们非常重要。

Bitwise operators

操作位涉及几个运算符。这些运算符如下：

• 一元位补运算符[~]：作为一元，这个运算符需要放在数字之前的单个操作数。这个 运算符获取数字的每一位并将其值翻转，因此 1 变为 0，反之亦然；例如，5 = 101，~5 = 010。
• 按位与 [&]：此运算符需要两个操作数，并放置在两个数字之间。此运算符 逐一比较两个数字 的位。它充当逻辑 AND (&&)，这意味着它仅在比较位等于 1 时才返回 1；例如，5 = 101, 7 = 111, 5 & 7 = 101 & 111 = 101 = 5。
• 按位或 [|]：此运算符 需要两个操作数并放置在两个 数字之间。该运算符将两个数字的 位一一进行比较。它充当逻辑 OR (||)，这意味着如果至少有一个比较位为 1（或两者），则返回 1。否则，返回 0；例如，5 = 101, 7 = 111, 5 | 7 = 101 | 111 = 111 = 7。
• 按位异或 (XOR) [^]：此运算符 需要两个操作数，放在两个数字之间。此运算符 将两个数字的位一一进行比较。仅当比较的位具有不同的值时，它才返回 1。否则，返回 0；例如，5 = 101, 7 = 111, 5 ^ 7 = 101 | 111 = 010 = 2。

下图是一个方便的工具，当您需要处理比特时，您应该密切关注它。基本上，它总结了位运算符的工作原理（我建议您在通读编码挑战部分时保持此表关闭）：

图 9.2 – 位运算符

此外，下图代表了一些对操作位非常有用的技巧。 0 表示法 表示零序列，而 1 表示法表示一序列：

图 9.3 – 按位提示

花点时间探索这些技巧。拿一张纸和一支笔，逐一检查。此外，尝试发现其他提示。

Bit shift operators

移位是处理位时常见的 操作。在这里，我们有 Signed Left Shift [<<]、Signed Right Shift [>>] 和 < strong class="bold">无符号右移 [>>>]。移位 适用于 byte (8-bit), short (16-位）、int（32 位）、long（64 位）和 字符（16位）；位移运算符不会抛出异常。

Signed Left Shift [<<]

带符号的 Left Shift 或简称 Left Shift 需要两个操作数。 Left Shift 获取第一个操作数（左侧操作数）的位模式并将其向左移动第二个 操作数（右侧操作数）给出的位置数）。

例如，下面是 23 左移 3 个位置的结果，23 <<< 3：

图 9.4 – 有符号左移

正如我们所见，整数 12 (10111) 的每一位 都向左移动了 3 个位置，而右侧的所有位置都自动用零填充。

重要的提示

以下是在某些情况下非常有用的两个提示：

1.将数字左移n个位置相当于乘以2n（例如，23 << 3等于 184，相当于 184 = 23 * 23)。

2.要移位的位置数自动减少到模32；即，23 << 35等价于23<< (35 % 32)，相当于 23 << 3.

Negative integers in Java

首先，重要的是要记住，二进制表示本身并不能告诉我们一个数字是否为负。这意味着计算机 需要一些规则来表示负数。通常，计算机以二的补码表示形式存储整数。 Java 也使用 这种表示。

简而言之，二进制补码表示采用负数的二进制表示并翻转（取反）其所有位。之后，它加 1 并将其附加到位符号的左侧。如果最左边的位为 1，则该数字为负数。否则，它是积极的。

让我们以 4 位整数 -5 为例。我们有一个符号位和三个值位。我们知道5（正数）表示为101，而-5（负数）表示为1011。这是通过翻转101使其变为010，加1得到011并附加到符号位的左侧（1）得到1011。粗体的 1 是符号位。所以，我们有一个符号位和三个值位。

另一种方法是 知道 -Q 的二进制表示（负 Q ) 作为一个 n-bit 数字是通过将 1 与 2 连接获得的n - 1 – Q。

Signed Right Shift [>>]

有符号右移或算术右移 [>>] 采用两个操作数。有符号右移获取第一个操作数（左侧操作数）的位模式，并将其向右移动第二个操作数（右侧操作数）给出的位置数操作数）通过保留符号。

例如，后面的 是-75 >> 的结果。 1（-75 是一个 8 位整数，其中符号位是 Most Significant Bit (MSB)）：

图 9.5 – 有符号右移

正如我们所见，-75 (10110101) 的每一位都向右移动了 1 个位置（注意 Least Significant Bit (LSB ) 已更改）并且 位符号被保留。

重要的提示

以下是在某些情况下非常有用的三个提示：

将数字右移 n 个位置相当于除以 2n（例如，24 >> 3 等于到 3，相当于 3 = 24/23)。

要移动的位置数自动减少到模 32；即，23>> 35等价于23>> (35% 32)，相当于 23>> 3.

（有符号的）二进制项中的所有 1 的序列以十进制形式表示 -1。

Unsigned Right Shift [>>>]

无符号右移，或 逻辑右移 [>>>]，需要两个操作数。无符号右移获取第一个操作数（左侧操作数）的位模式并将其向右移动第二个操作数（右侧操作数）给出的位置数。 MSB 设置为 0。这意味着，对于正数，有符号和无符号右移返回相同的结果，而负数始终变为正数。

比如后面的就是-75>>>的结果。 1（-75 是一个 8 位整数，其中符号位是 MSB）：

图 9.6 – 无符号右移

重要的提示

要移动的位置数自动减少到模 32；也就是说，23>>> 35等价于23>>> (35 % 32)，这相当于 23 >>> 3.

现在您已经了解了什么是位移运算符，是时候了解更多提示和技巧了。

Tips and tricks

操作位涉及在与位操作员一起工作时的高超技能，并了解一些技巧和窍门。您已经在本章前面看到了几个技巧。现在，让我们添加更多内容作为项目符号列表：

• 如果我们将一个数与自身 XOR[^] 偶数次，则结果为 0 (x ^ x = 0; x ^ x ^ x^ x = (x ^ x) ^ ( x ^ x) = 0 ^ 0 = 0)。
• 如果我们将一个数字与自身 XOR[^] 奇数次，那么结果就是那个数字 (x ^ x ^ x = (x ^ (x ^ x)) = (x ^ < /em>0) = x; x ^ x ^ x ^ x ^ x = (x ^ (x ^ x) ^ (x ^ x)) = (x ^ 0 ^ 0) = x)。
• 我们可以用 p > 计算表达式 p % q 的值； 0、q> 0，其中 q 是 2 的幂；即p& （q - 1）。 ComputeModuloDivision 是一个简单的应用程序，您可以在其中看到这一点。
• 对于给定的正整数 p，如果 ((p & 1) != 0) 和即使 ((p & 1) == 0)。 OddEven 是一个简单的应用程序，您可以在其中看到这一点。
• 对于两个给定的数字p和q，我们可以说p 等于 q if ((p ^ q) == 0)。 CheckEquality 是一个简单的应用程序，您可以在其中看到这一点。
• 对于两个给定的整数 p 和 q，我们可以通过 p 交换它们= p ^ q ^ (q = p)。 SwapTwoIntegers 是一个简单的应用程序，您可以在其中看到这一点。

好的，是时候解决一些编码挑战了。

在接下来的 25 个编码挑战中，我们将利用位操作的不同方面。由于这类问题确实是脑筋急转弯，所以在面试中是的首选。理解一个操作位的代码片段不是一件容易的事，所以花点时间剖析每个问题和代码片段。这是获得一些模式和模板以解决此类问题的唯一方法。

下图包含一组四个位掩码，这些位掩码在您的工具带中很重要：

图 9.7 – 位掩码

它们可用于解决需要操作位的各种问题。

Coding challenge 1 – Getting the bit value

问题：考虑 32 位整数，n。编写一段 代码，返回 n 在给定位置 k 的位值。

解决方案：让我们考虑 n=423。它的二进制表示是 110100111。我们怎么能说位置 k=7 的位的值是多少（位置 7 的粗体位的值为 1）？解决方案包括将给定数字右移 k 个位置 (n >> k）。这样，kth 位变为位置 0 (11 0100111 >> 7 = 000000011)。接下来，我们可以将 AND [&] 运算符应用为 1 & （n >>k）：

图 9.8 – 二进制表示

如果位置 0 的位的值为 1，则 AND[&] 运算符将返回 1；否则，它将返回 0。就代码而言，我们有以下内容：

public static char getValue(int n, int k) {
  int result = n & (1 << k);
  if (result == 0) {
    return '0';
  }
  return '1';
}

另一种方法包括替换表达式 1 & (n >> k) 与表达式 n & （1 <k）。花点时间尝试剖析它。完整的应用程序称为GetBitValue。

Coding challenge 2 – Setting the bit value

亚马逊、谷歌、Adobe、微软，Flipkart

问题：考虑一个 32 位整数，n。编写 设置n 的位 值的代码片段给定位置，k 为 0 或 1。

解决方案：让我们考虑 n=423。它的二进制表示是 110100111。我们如何将位置 k=7（现在为 1）的位设置为 0？将位运算符表放在我们面前有助于我们看到 AND[&] 运算符是唯一具有两个操作数的运算符，它允许我们编写 1 & 0 = 0 或第 7th 位 & 0 = 0。此外，我们有 1 & 1 = 1, 0 & 1 = 0 和 0 & 0 = 0，因此我们可以将位掩码设为 1...101111111 并编写以下内容：

图 9.9 – 二进制表示

这正是我们想要的。我们希望将第 7th 位从 1 变为 0，其余的保持不变。但是我们如何获得 1...101111... 掩码？好吧，您需要了解两个位掩码。首先，一个位掩码，它有一个 1，其余的是 0（10000...）。这可以通过将 1 左移 k 个位置来获得（例如，可以将位掩码 1000 获得为 1 << 3，但如果我们将其表示为 32 -位掩码，我们得到 00000000 00000000 00000000 0001000）。另一个位掩码包含 0，其余为 1 (01111...)。这可以通过将一元按位补码运算符 [~] 应用于位掩码 10000....（例如，~(1000) = 0111，尽管如果我们将其表示为 32 位掩码，我们得到 11111111 11111111 11111111 1110111）。因此，我们可以获得 1...101111... 位掩码为 ~(1 <k)。最后，我们所要做的就是使用 AND[&] 运算符，如下面的代码所示：

public static int setValueTo0(int n, int k) {       
  return n & ~(1 << k);
}

如果我们取 k=3、4 或 6，那么我们得到 0 & 0 = 0。

让我们考虑 n=295。它的二进制表示是 100100111。我们如何将位置 k=7（现在为 0）设置为 1？将位运算符表摆在我们面前有助于我们看到 OR[|] 和 XOR[^] 运算符是具有两个操作数的运算符，它们允许我们写出 0 | 1 = 1 或 0 ^ 1 = 1，分别。

或者，我们可以写成 7th | 1 = 1 和 7th ^ 1 = 1。

通过进一步 一步，我们可以看到在 OR[|] 运算符的情况下，我们可以编写以下内容：

1 | 1 = 1，而在 XOR[^] 运算符的情况下，我们写成 1 ^ 1 = 0。

由于我们想将第 7th 位的值从 0 变为 1，我们可以使用这两个运算符中的任何一个。但是，如果 k 表示一个初始值为 1 的位，那么 1 ^ 1 = 0 不再帮助我们，而 1 | 1 = 1 正是我们想要的。所以在这里，我们应该使用 10000... 位掩码，如下所示：

图 9.10 – 二进制表示

在代码方面，我们有以下内容：

public static int setValueTo1(int n, int k) {       
  return n | (1 << k);
}

如果我们取 k=0、1、2、5 或 8，那么我们得到 1 | 1 = 1。

完整的应用程序称为SetBitValue。

Coding challenge 3 – Clearing bits

亚马逊、谷歌、Adobe

问题：考虑一个 32 位 整数，n。编写代码片段，清除MSB和给定 n 位（将它们的值设置为0）类="斜体">k。

解决方案：让我们考虑 n=423。它的二进制表示是110100111。我们如何清除 MSB 和位置 k=6 之间的位，以便有 110 位？将位运算符表放在我们面前有助于我们看到我们需要一个类型为 00011111 的位掩码。让我们看看如果我们在 n 和这个位掩码：

图 9.11 – 二进制表示

因此，我们清除了 MSB 和 k=6 之间的 位。一般来说，我们需要一个位掩码，在 MSB 和 k 之间包含 0（包括），在 k 之间包含 1（不包括) 和 LSB。我们可以通过将 1 的位左移 k 个位置来做到这一点（例如，对于 k=6，我们得到 1000000 ) 并减去 1。通过这种 方式，我们获得了所需的位掩码 0111111。因此，就代码而言，我们有以下内容：

public static int clearFromMsb(int n, int k) {        
  return n & ((1 << k) - 1);
}

如何清除给定 k 和 LSB 之间的位？让我给你看一下代码：

public static int clearFromPosition(int n, int k) {        
  return n & ~((1 << k) - 1);
}

现在，花点时间剖析这个解决方案。此外，我们可以用这个解决方案替换这个解决方案：n & (-1 << (k + 1))。

再次，使用纸和笔，一步一步地进行。完整的应用程序称为ClearBits。

Coding challenge 4 – Summing binaries on paper

问题：考虑几个正32位整数。拿一支笔和一些纸，告诉我你如何总结它们的二进制表示。

注意：这不是一个编码挑战，但了解这一点很重要。

解决方案：对二进制数求和有多种方法。一个简单的方法是执行以下操作：

1. 对当前列的所有位求和（第一列是 LSB 的列）。
2. 将结果转换为二进制（例如，通过连续除以 2）。
3. 保留最右边的位作为结果。
4. 将剩余位携带到其余列中（每列一位）。
5. 转到下一列并从 步骤 1 开始重复。

一个例子将澄清事情。让我们添加 1 (1) + 9 (1001) + 29 (011101) + 124 (1111100) = 163 (10100011)。

下图表示对这些数字求和的结果：

图 9.12 – 二进制数相加

现在，让我们一步一步看这个（加粗部分）：

• 第 0 列的总和位：1 + 1 + 1 + 0 = 3 = 11 1
• 第 1 列的总和位：1 + 0 + 0 + 0 = 1 = 1 1
• 第 2 列的总和位：0 + 1 + 1 = 2 = 10 0
• 第 3 列的总和位：1 + 1 + 1 + 1 = 4 = 100 0
• 第 4 列的总和位：0 + 1 + 1 = 2 = 10 0
• 第 5 列的总和位：1 + 1 + 0+1 = 3 = 1< /强>1 1
• 第 6 列的总和位：1 + 1 = 2 = 10 0
• 第 7 列的总和：1 = 1 = 1 1

因此， 结果为 10100011。

Coding challenge 5 – Summing binaries in code

问题：考虑两个 32 位整数，q 和 p。编写一段代码，使用它们的二进制 表示来计算 q + p .

解决方案：我们可以尝试实现上一个编码挑战中提出的算法，或者我们可以尝试其他方法。这种方法引入了一个有用的等式：

注意 AND[&] 和 XOR[^] 位运算符的存在。如果我们表示 p & q 与 and，以及 p ^ q 与 xor，那么我们可以这样写：

如果 p 和 q 没有公共位，那么我们可以将其简化为：

例如，如果 p = 1010 且 q = 0101，则 p & q = 0000。由于 2*0000 = 0，我们仍然使用 p + q< /em> = xor，或 p + q = 1111。

但是，如果 p 和 q 有共同的位，那么我们必须处理添加 和和异或。因此，如果我们强制 and 表达式返回 0，, and + xor 可以解决。这可以通过递归来完成。

通过递归，我们可以将递归的第一步写成：

或者，如果我们表示 and{1} = 2 * and & 异或，和 异或{1} = 2 * 和 ^ xor 其中 {1} 表示递归的一步，那么我们可以这样写：

但是这个 递归什么时候停止呢？嗯，当两个位序列（p 和 q< /em>) 在 and{n} 表达式中返回 0。所以，在这里，我们强制 and 表达式返回 0。

在代码方面，我们有以下内容：

public static int sum(int q, int p) {
  int xor;
  int and;
  int t;
  and = q & p;
  xor = q ^ p;
  // force 'and' to return 0
  while (and != 0) {
    and = and << 1; // this is multiplication by 2
    // prepare the next step of recursion
    t = xor ^ and;
    and = and & xor;
    xor = t;
  }
  return xor;
}

完整 应用程序称为SummingBinaries。

Coding challenge 6 – Multiplying binaries on paper

问题：考虑两个正32位整数，q和 p。拿一些纸和一支笔，告诉我如何将这两个数字的二进制表示相乘（ q* p）。

注意：这不是一个编码挑战，但了解这一点很重要。

解决方案：当我们将二进制数相乘时，我们必须记住，将二进制数乘以 1 会得到完全相同的二进制数，而将二进制数乘以 0 会得到完全相同的二进制数返回0。两个二进制数相乘的步骤如下：

1. 从最右边的列（第 0 列）开始，将第二个二进制数的每一位乘以第一个二进制数的每一位。
2. 总结结果。

让我们做 124 (1111100) * 29 (011101) = 3596 (111000001100)。

下图表示我们计算的结果：

图 9.13 – 二进制数相乘

因此，我们将 29 的每一位乘以 124 的每一位。接下来，我们将这些二进制文件相加，正如您在 编码挑战的前面看到的 4 – 在纸上汇总二进制文件部分。

Coding challenge 7 – Multiplying binaries in code

亚马逊、谷歌、Adobe

问题：考虑两个 32 位整数，q 和 p。编写一段代码，使用它们的二进制 表示来计算 q * p .

解决方案：我们可以尝试实现之前的编码挑战中提出的算法，或者我们可以尝试其他方法。这种方法首先假设 p=1，所以在这里，我们有 q*1=q。我们知道任何q乘以1就是q，所以我们可以说q< /em>*1 跟随下一个总和（我们从 0 到 30，因此我们忽略位置 31 上的有符号位）：

图 9.14 – 在代码中乘以二进制

例如，如果 q=5 (101)，则 5 * 1 = 0*230 + 0*229 + ...1*22 + 0*21 + 1 *20 = 5。

所以，5 * 1 = 5。

到目前为止，这没什么大不了的，但让我们继续 5 * 2；也就是说，有 101 * 10。如果我们认为 5 * 2 = 5 * 0 + 10 * 1，那么这意味着 101 * 10 = 101 * 0 + 1010 * 1。所以，我们将 5 左移 一个位置，我们将 2 右移一个位置。

让我们继续 5 * 3。这是 101 * 011。但是，5 * 3 = 5 * 1 + 10 * 1。因此它就像 101 * 1 + 1010 * 1。

让我们继续 5 * 4。这是 101 * 100。但是，5 * 4 = 5 * 0 + 10 * 0 + 20 * 1。因此，它就像 101 * 0 + 1010 * 0 + 10100 * 1。

现在，我们可以开始 来查看遵循这些步骤的模式（最初，结果=0）：

1. 如果 p 的 LSB 为 1，那么我们写如下：
   

   图9.15 - p的LSB为1

2. 我们将 q 左移一位，逻辑右移 p 一位。
3. 我们从 step 1 开始重复，直到 p 为 0。

如果我们把这三个步骤写成代码，那么我们得到如下输出：

public static int multiply(int q, int p) {
  int result = 0;
  while (p != 0) {
    // we compute the value of q only when the LSB of p is 1            
    if ((p & 1) != 0) {
      result = result + q;
    }
    q = q << 1;  // q is left shifted with 1 position
    p = p >>> 1; // p is logical right shifted with 1 position
  }
  return result;
}

完整的应用程序是称为MultiplyingBinaries。

Coding challenge 8 – Subtracting binaries on paper

问题：考虑两个正的 32 位整数，q 和 p .拿一些纸和笔，告诉我你如何减去这两个数字的二进制表示（q-p）。

注意：这不是一个编码挑战，但了解这一点很重要。

解决方案：二进制数相减可以求0减1。主要我们知道1减1为0，0减0为0，1减0为1. 要计算 0 减 1，我们必须遵循以下步骤：

1. 从当前列中，我们搜索左列，直到找到一点 1。
2. 我们借用这一位并将其作为两个值 1 放在上一列中。
3. 然后，我们从前一列借用这两个值 1 中的一个作为其他两个 1。
4. 对每一列重复第 3 步，直到我们到达当前列。
5. 现在，我们可以执行计算了。
6. 如果我们遇到另一个 0 减 1，那么我们从 step 1 开始重复这个过程。

让我们做 124 (1111100) - 29 (011101) = 95 (1011111)。

下图表示我们计算的结果：

图 9.16 – 减去二进制数

现在，让我们一步一步来看看：

1. 从 列 0 开始，所以从 0 减去 1。我们在左列中搜索，直到找到一点 1。我们在第 2 列找到它（该位对应到 22=4)。我们在第 1 列中借用该位并将其用作 1 的两个值（换句话说，2 中的两个是 21+21< /跨度>）。我们在第 0 列中借用这两个 1 值之一（这是 21=2）并将它们用作另外两个 1 值（换句话说，两个 1是 20+20)。现在，我们可以进行计算，因为 2 减 1 等于 1。我们记下 1 并移至第 1 列。
2. 我们继续第 1 列，因此 1 减去 0 等于 1。我们记下 1 并移至第 2 列。
3. 然后我们继续第 2 列，因此 0 减去 1。我们在左列中搜索，直到找到一点 1。我们在第 3 列找到它（该位对应于 2 3=8)。我们从第 2 列借用这个位并将其用作 1 的两个值（换句话说，2 中的两个是 22+22< /跨度>）。现在，我们可以进行计算，因为 2 减 1 等于 1。我们记下 1 并移至第 3 列。
4. 我们继续第 3 列，所以用 0 减去 1。我们在左列中搜索，直到找到一点 1。我们在第 4 列找到它（该位对应于 24 =16）。我们在第 3 列中借用这个位并将其用作 1 的两个值（换句话说，2 中的两个是 23+23< /跨度>）。现在，我们可以进行计算，因为 2 减 1 等于 1。我们记下 1 并移至第 4 列。
5. 我们继续第 4 列，所以用 0 减去 1。我们在左列中搜索，直到找到一点 1。我们在第 5 列找到它（该位对应于 25 =32）。我们在第 4 列中借用这个 位并将其用作两个值 1（换句话说，2 中的两个是 24 +24）。现在，我们可以进行计算，因为 2 减 1 等于 1。我们记下 1 并移至第 5 列。
6. 我们继续第 5 列，所以用 0 减去 0。我们记下 0 并移至第 6 列。
7. 我们继续第 6 列，所以用 1 减去 0。我们写下 1，然后我们就完成了。

所以，结果是 1011111。

Coding challenge 9 – Subtracting binaries in code

问题：考虑两个 32 位 整数，q 和 p。编写一段代码，使用它们的二进制表示来计算 q - p。

解决方案：我们已经从之前的编码挑战中知道，减去二进制数可以减少计算 0 减 1。此外，我们知道如何使用 借用 技术解决 0 减 1。除了借用技术，重要的是要注意 |q - p| = q ^ p;例如：

|1 - 1| = 1 ^ 1 = 0, |1 - 0| = 1 ^ 0 = 1, |0 - 1| = 0 ^ 1 = 1 和 |0 - 0| = 0 ^ 0 = 0。

基于这两条语句，我们可以实现两个二进制的减法，如下：

public static int subtract(int q, int p) {
  while (p != 0) {
    // borrow the unset bits of q AND set bits of p
    int borrow = (~q) & p;
    // subtraction of bits of q and p 
    // where at least one of the bits is not set
    q = q ^ p;
    // left shift borrow by one position            
    p = borrow << 1;
  }
  return q;
}

完整的应用程序称为SubtractingBinaries。

Coding challenge 10 – Dividing binaries on paper

问题：考虑两个正的 32 位整数，q 和 p。拿一些纸和一支笔，告诉我你是如何划分这两个数字的二进制表示的（q/p）。

注意：这不是一个编码挑战，但了解这一点很重要。

解决方案：二进制除法只有两种可能：0或1。除法涉及红利(q)，除数(p),< /em> 商和 余数。例如，我们知道 11(dividend) / 2(divisor) = 5(quotient) 1(remainder)。或者，在二进制表示中，我们有 1011（股息）/10（除数）= 101（商）1（余数）

我们首先将除数与股息的 MSB 进行比较（我们称其为 sub-dividend）并执行以下操作：

一个。如果除数不适合子股息（除数 > 子股息），那么我们将 0 附加到商。

a.a) 我们将股息的下一位附加到子股息并从 步骤 a 继续。

湾。如果除数适合子股息（除数 <= 子股息），那么我们将 1 附加到商。

b.a) 我们从当前的子股息中减去 除数。

b.b) 我们将下一位股息附加到减法的结果（这是新的子股息），然后从 step a).

C。当我们处理完被除数的所有位后，我们应该得到商和余数，这是除法的结果。

c.a) 我们可以在这里停下来，用得到的商和余数来表达结果。

c.b) 我们可以将一个点 (".") 附加到商上，并将 0 附加到当前余数（这是新的子股息），然后从 step a 直到余数为 0 或者我们对结果感到满意。

下图表示 11/2 分割：

图 9.17 – 二进制数相除

现在，让我们一步一步看这个（关注上图的左侧）：

• 分红 = 1, 10 > 1 自 2 > 1，因此我们将 0 附加到商。
• 分红 = 10, 10 = 10 因为 2 = 2，因此我们将 1 附加到商。
• 做减法，10 - 10 = 0。
• 分红 = 01, 10 > 01 自 2 > 1，因此我们将 0 附加到商。
• 分红 = 011, 10 < 011 自 2 ＜ 3，因此我们将 1 附加到商。
• 做减法，011 - 10 = 1。
• 从被除数中处理没有更多位，因此我们可以说11/2的商为101（即5），余数为1。

如果您查看上图的右侧，您会看到我们可以通过应用给定的 step c.b 继续计算直到余数为 0。

Coding challenge 11 – Dividing binaries in code

亚马逊、谷歌、Adobe

问题：考虑两个 32 位整数，q 和 p。编写一段代码，使用它们的二进制 表示来计算 q/p .

解决方案：我们可以使用多种方法来划分两个二进制文件。让我们专注于实现一个只计算商的解决方案，这意味着我们跳过余数。

这种方法非常简单。我们知道一个 32 位整数包含对我们来说在 31 和 0 之间计数的位。我们所要做的就是将除数 (p) 左移 i 个位置 (i=31, 30, 29, ..., 2, 1, 0) 并检查结果是否小于股息（q）。每次我们找到这样的位时，我们都会更新 ith 位的位置。我们累积结果并将其传递给下一个位置。以下代码不言自明：

private static final int MAX_BIT = 31;
...
public static long divideWithoutRemainder(long q, long p) {
  // obtain the sign of the division
  long sign = ((q < 0) ^ (p < 0)) ? -1 : 1;
  // ensure that q and p are positive
  q = Math.abs(q);
  p = Math.abs(p);
  long t = 0;
  long quotient = 0;
  for (int i = MAX_BIT; i >= 0; --i) {
    long halfdown = t + (p << i);
    if (halfdown <= q) {
      t = t + p << i;
      quotient = quotient | 1L << i;
    }
  }
  return sign * quotient;
}

完整的应用程序称为DividingBinaries。它还包含 计算 余数的实现。

Coding challenge 12 – Replacing bits

亚马逊、谷歌、Adobe

问题：考虑两个正 32 位整数，q 和 p，以及两个位位置，i 和 j。编写一段代码 替换位置 i 之间 q 中的位和 j 与 p 的位。您可以假设，在 i 和 j, 之间有足够的空间来容纳 p。

解决方案：让我们考虑 q=4914（二进制，1001100110010），p =63（二进制，111111），i=4，和 j=9。下图显示了我们拥有的和想要获得的：

图 9.18 – 替换 i 和 j 之间的位

正如我们所见，该解决方案应完成三个主要步骤。首先，我们需要清除 i 和 j 之间的 q 位.其次，我们需要将 p 左移 i 个位置（这样，我们将 p 在正确的位置）。最后，我们将 p 和 q 合并为最终结果。

为了清除 i 和 j 之间的 q 位（设置这些位为 0，无论它们的初始值如何），我们可以使用 AND[&] 运算符。我们知道只有 1 & 1 返回 1，所以如果我们有一个在 i 和 j 之间包含 0 的位掩码，那么 q & 位掩码 将导致在 i 和 j 自 1 & 0和0& 0 为 0。而且，位的 MSB 和 j （独占）和 i （独占）和 LSB 之间掩码，我们应该只有 1 的值。这样，q & 位掩码 将保留 q 位，因为 1 & 1 = 1 和 0 & 1 = 0。所以，我们的位掩码应该是 1110000001111。让我们看看它的工作情况：

图 9.19 – 位掩码 (a)

但是我们怎样才能得到这个面具呢？我们可以通过 OR[|] 操作符得到它，如下：

图 9.20 – 位掩码 (b)

1110000000000位掩码可以通过-1左移j+1个位置得到，而0000000001111位掩码可以通过左移1i 个位置并减去 1。

在这里，我们解决了前两个步骤。最后，我们需要把p放在正确的位置。这很简单：我们只需将 p 左移 i 个位置。最后，我们在 q 和 i 和 之间应用 OR[|] 运算符j，以及移位的p：

图 9.21 – 二进制表示

我们完成了！现在，让我们将其放入代码中：

public static int replace(int q, int p, int i, int j) {
  int ones = ~0; // 11111111 11111111 11111111 11111111          
  int leftShiftJ = ones << (j + 1);
  int leftShiftI = ((1 << i) - 1);
  int mask = leftShiftJ | leftShiftI;
  int applyMaskToQ = q & mask;
  int bringPInPlace = p << i;
  return applyMaskToQ | bringPInPlace;
}

完整的 应用程序是称为ReplaceBits。

Coding challenge 13 – Longest sequence of 1

亚马逊、Adobe、微软、 Flipkart

问题：考虑一个 32 位整数，n。 101的序列可以认为是111。编写一段代码，计算1的最长序列的长度。

解决方案：我们来看几个例子（下面三列分别代表整数，它的二进制表示，长度1）的最长序列：

图 9.22 – 三个例子

如果我们知道 n & 1 = 1 如果 n 的 LSB 为 1 并且 n &如果 n 的 LSB 为 0，则 0 = 0。让我们关注第一个示例 67534 (10000011111001110)。在这里，我们执行以下操作：

• 初始化最长序列 = 0。
• 应用 AND[&]:10000011111001110 & 1 = 0，最长序列 = 0。
• 右移并应用 AND[&]:1000001111100111 & 1 = 1，最长序列 = 1。
• 右移并应用 AND[&]:100000111110011 & 1 = 1，最长序列 = 2。
• 右移并应用 AND[&]:10000011111001 & 1 = 1，最长序列 = 3。
• 右移并应用 AND[&]:1000001111100 & 1 = 0，最长序列 = 0
• 右移并应用 AND[&]:100000111110 & 1 = 0，最长序列 = 0。
• 右移并应用 AND[&]:10000011111 & 1 = 1，最长序列 = 1。
• 右移并应用 AND[&]:1000001111 & 1 = 1，最长序列 = 2。
• 右移并应用 AND[&]:100000111 & 1 = 1，最长序列 = 3。
• 右移并应用 AND[&]:10000011 & 1 = 1，最长序列 = 4。
• 右移并应用 AND[&]:1000001 & 1 = 1，最长序列 = 5。
• 右移并应用 AND[&]:100000 & 1 = 0，最长序列 = 0。

因此，只要我们在最长的 1 序列中没有 有任何 0 交错，我们就可以实现上述方法。但是，此方法不适用于第三种情况 339809 (1010010111101100001)。在这里，我们需要做一些额外的检查；否则，最长序列的长度将等于 4。但是由于 101 可以被视为 111，因此 正确答案是 9。这意味着当我们有 n & 1 = 0，我们必须进行以下检查（主要是检查当前位 0 是否被两位 1 保护为 101）：

• 检查下一位是 1 还是 0，(n & 2) == 1 或 0
• 如果下一位为 1，则检查前一位是否为 1

我们可以把它写成如下代码：

public static int sequence(int n) {
  if (~n == 0) {
    return Integer.SIZE; // 32
  }
  int currentSequence = 0;
  int longestSequence = 0;
  boolean flag = true;
  while (n != 0) {
    if ((n & 1) == 1) {
      currentSequence++;
      flag = false;
    } else if ((n & 1) == 0) {
      currentSequence = ((n & 0b10) == 0) // 0b10 = 2
        ? 0 : flag 
        ? 0 : ++currentSequence;
      flag = true;
    }
    longestSequence = Math.max(
      currentSequence, longestSequence);
    n >>>= 1;
  }
  return longestSequence;
}

完整的应用程序是称为LongestSequence。

Coding challenge 14 – Next and previous numbers

Adobe、微软

问题：考虑一个 32 位整数，n。编写一段代码，返回 包含完全相同数量的 1 位的下一个最大数字。

解决方案：让我们考虑 n=124344 (11110010110111000)。要获得另一个具有相同数字 的 1 位的数字，我们必须翻转一位 1 将其变为 0，再翻转一位 0 将其变为 1。结果number 将与给定的不同，并且包含相同数量的 1 位。现在，如果我们希望这个数字大于给定的数字，那么从 0 翻转到 1 的位应该在从 1 翻转到 0 的位的左侧。换句话说，有两个位位置， i 和 j，并将位置 i 的位从 1 翻转到0 和位置 j 的位从 0 到 1，如果 i >，这将导致新数字小于给定数字j，如果 i < 则更大j，分别。

这意味着我们必须找到 0 的第一个位，它的右边不只包含零（换句话说，非尾随零的第一个位）。这样，如果我们将这个位从 0 翻转到 1，那么我们知道在这个位的右边至少有一位 1 可以从 1 翻转到 0。这意味着我们得到一个更大的数相同数量的 1 位。下图以图形形式显示了这些数字：

图 9.23 – 非尾随零

因此，对于我们的数字，第一个非尾随零位于第 6 位。如果我们将该位从 0 翻转到 1，则结果数字大于给定数字。但是现在，我们必须从该位的右侧选择一个位，它将从 1 翻转到 0。基本上，我们必须在位置 3、4 和 5 之间进行选择。但是，这是正确的逻辑吗？请记住，我们必须返回下一个最大的数字，而不是任何大于给定数字的数字。翻转位置 5 的位比翻转位置 3 或 4 的位要好，但这不是 下一个最大的数字。查看以下关系（下标为二进制表示对应的十进制值）：

图 9.24 – 几种关系

到目前为止，我们可以得出结论 11110010111011000124376 看起来是正确的选择。但是，我们也应该注意以下几点：

11110010111011000124376 > 11110010111000011124355

因此，如果我们计算位置 6（不包括）和 0（我们用 k=3 表示）之间 1 的位数，则获得下一个最大的数，清除所有位置 6（不包括）和 0（将它们设置为 0）之间的位，并将位置 kk-1 位设置为 1 >-1 和 0。

好的;到目前为止，一切都很好！现在，让我们把这个算法写成代码。首先，我们需要找到非尾随零的第一位的位置。这意味着我们需要将尾随零的计数与 1 的计数相加，直到我们得到第一个 0。计算尾随零可以如下完成（我们正在处理 n< /em> 因为我们不想移动给定数字的位）：

int copyn = n;
int zeros = 0;
while ((copyn != 0) && ((copyn & 1) == 0)) {
  zeros++;
  copyn = copyn >> 1;
}

计数 1 直到第一个 0 可以这样完成：

int ones=0;
while ((copyn & 1) == 1) {
  ones++;
  copyn = copyn >> 1;
}

现在，marker = zeros + ones 为我们提供了 搜索位置。接下来，我们将该位置的位从 0 翻转到 1，并清除该位置（不包括）和 0 之间的所有位：

n = n | (1 << marker);

在我们的例子中，marker=6。此行的 效果产生以下输出：

图 9.25 – 输出 (1)

n = n & (-1 << marker);

图 9.26 – 输出 (2)

最后，我们将 (ones - 1) 和 0 之间的位设置为 1：

n = n | (1 << (ones - 1)) - 1;

在我们的例子中，ones=3。此行的效果产生以下输出：

图 9.27 – 输出 (3)

所以，最终的结果是11110010111000011，也就是124355。所以，最终的方法如下所示：

public static int next(int n) {
  int copyn = n;
  int zeros = 0;
  int ones = 0;
  // count trailing 0s
  while ((copyn != 0) && ((copyn & 1) == 0)) {
    zeros++;
    copyn = copyn >> 1;
  }
  // count all 1s until first 0
  while ((copyn & 1) == 1) {
    ones++;
    copyn = copyn >> 1;
  }
  // the 1111...000... is the biggest number 
  // without adding more 1
  if (zeros + ones == 0 || zeros + ones == 31) {
    return -1;
  }
  int marker = zeros + ones;
  n = n | (1 << marker);
  n = n & (-1 << marker);
  n = n | (1 << (ones - 1)) - 1;
  return n;
}

完整的应用程序称为 NextNumber。它还包含一个方法，该方法返回包含完全相同数量的 1 位的下一个最小数字。接受挑战并尝试自己提供解决方案。完成后，只需将您的解决方案与捆绑代码中的解决方案进行对比。作为提示，您将需要尾随 1 的数量（我们用 k 表示）和紧随尾随 1 左侧的 0 数量，直到您到达第一个 1 . 将这些值相加将为您提供应该从 1 翻转到 0 的位的位置。接下来，清除该位置右侧的所有位并设置 (k + 1) 位到该位置右侧的 1。

Coding challenge 15 – Conversion

亚马逊、谷歌、Adobe

问题：考虑两个正32位整数，q 和 p。编写一段代码，计算我们应该在 q 中翻转的位数，以便将其转换为 p。

Solution：如果我们观察到 XOR[^] 运算符仅在操作数不同时返回 1，那么这个问题的解决方案就很清楚了。让我们考虑 q = 290932 (1000111000001110100) 和 p = 352345 (1010110000001011001)。让我们应用 XOR[^] 运算符：

图 9.28 – 转换

换句话说，如果我们用 xor (< em class="italic">xor = q ^ p)，那么我们要做的就是计数xor 中 1 的位数（在我们的示例中，我们有 6 个 1）。这可以使用 AND[&] 运算符来完成，只为 1 & 返回 1。 1 = 1，所以我们可以计算 xor & xor 中的每一位为 1。每次比较后，我们将 xor 右移一个位置。代码自己说：

public static int count(int q, int p) {
  int count = 0;
  // each 1 represents a bit that is 
  // different between q and p
  int xor = q ^ p;
  while (xor != 0) {
    count += xor & 1; // only 1 & 1 = 1
    xor = xor >> 1;
  }
  return count;
}

完整的应用程序 称为转换。

Coding challenge 16 – Maximizing expressions

问题：考虑两个 32 位正整数，q 和 p，其中q≠p. q和 p 最大化表达式 ( q AND s) * ( p AND s)，其中 AND 是逻辑运算符 [&]？

解决方案：这是一种听起来很难但非常简单的问题。让我们从一个简单的a * b开始。 a * b 什么时候达到最大值？好吧，让我们考虑 b = 4。a * 4 何时达到最大值？让我们写一些测试用例：

a = 1, 1 * 4 = 4

a = 2, 2 * 4 = 8

a = 3, 3 * 4 = 12

a = 4, 4 * 4 = 16

所以，当 a = b 时，我们已经达到最大值 16。但是，a 可以是 5 和 5 * 4 = 20 > 16. 这是正确的，但这意味着 b 也可以是 5，所以 5 * 5 =, 25 > 20. 这与数学演示相去甚远，但我们可以注意到 a * b 在 a = b 时处于最大值>。

对于那些对数学演示感兴趣的人，假设我们有以下内容：

图 9.29 – 最大化表达式 (1)

这意味着我们有以下内容：

图 9.30 – 最大化表达式 (2)

此外，这意味着我们有以下内容：

图 9.31 – 最大化表达式 (3)

现在，如果我们说 a * b 是 a = b 时的最大值，那么让我们表示 a = (q AND s) 和 b = (p AND s)。所以， (q AND s) * (p AND s) 在 (q AND s) = (p AND s）。

让我们考虑 q = 822 (1100110110) 和 p = 663 (1010010111)。 q 的 LSB 为 0，而 p 的 LSB 为 1，所以我们可以这样写：

(1 AND s) = (0 AND s) → s = 0 → (1 & 0) = (0 & 0) = 0

如果我们将 q 和 p 右移 1 个位置，则 我们发现q 的 LSB 为 1，p 的 LSB 为 1：

图 9.32 – 将 q​​ 和 p 右移 1 个位置

在这里，我们还有两种情况可以直观地理解如下：

图 9.33 – 两种情况

在这里，我们可以看到我们的问题的答案是q & p = s。让我们看看这个在工作中：

图 9.34 – 答案

答案是 1000010110，即 534。这意味着 (822 AND 534) = (663 AND 534)。

Coding challenge 17 – Swapping odd and even bits

Adobe、微软、Flipkart

问题：考虑一个正32位整数，n。编写一段代码，交换这个整数的奇数位和偶数位。

解决方案：让我们考虑 n = 663 (1010010111)。如果我们手动执行交换，那么我们应该获得0101101011。我们可以分两步完成：

1. 我们取奇数位并将它们向右移动一个位置。
2. 我们取偶数位并将它们向左移动一个位置。

但是我们怎么能做到这一点呢？

我们可以通过 AND[&] 运算符和在奇数位置包含 1 位的位掩码获取奇数位：10101010101010101010101010101010。让我们看看这个实际操作：

图 9.35 – 交换奇数位和偶数位 (1)

结果显示 1010010111 在位置 1、7 和 9 包含奇数位 1。接下来，我们将结果 1010000010 向右移动一个位置。这导致 0101000001。

我们可以通过 AND[&] 运算符和在偶数位置包含 1 位的位掩码获取偶数位：1010101010101010101010101010101。让我们看看这个实际操作：

图 9.36 – 交换奇偶位 (2)

结果显示 1010010111 在位置 0、2 和 4 处包含 1 的偶数位。接下来，我们将结果 0000010101 向左移动一个位置。这导致 0000101010。

要获得最终结果，我们只需对这两个结果应用 OR[|] 运算符即可：

图 9.37 – 最终结果

最终结果是 0101101011。实现遵循这些步骤ad litteram，所以这是简单明了：

public static int swap(int n) {
  int moveToEvenPositions
    = (n & 0b10101010101010101010101010101010) >>> 1;
  int moveToOddPositions
    = (n & 0b1010101010101010101010101010101) << 1;
  return moveToEvenPositions | moveToOddPositions;
}

完整的 应用程序称为SwapOddEven。

Coding challenge 18 – Rotating bits

亚马逊、谷歌、Adobe、微软，Flipkart

问题：考虑一个正的 32 位整数，n。编写一段代码，将 k 位向左或向右旋转。通过 轮换，我们了解到在二进制表示的一端脱落的位被发送到另一端。因此，在左旋转中，从左端掉落的位被发送到右端，而在右旋转中，从右端掉落的位被发送到左端。

解决方案：让我们关注左旋转（通常，右旋转解决方案是镜像左旋转解决方案）。我们已经知道，通过将 k 位向左移动，我们将这些位向左移动，并且用零填充空白点。但是，为了代替这些零，我们必须放置从左端掉下来的位。

让我们考虑 n= 423099897 (00011001001101111111110111111001) 和 k=10，所以我们向左旋转 10 位。下图突出显示了下降位和最终结果：

图 9.38 – 左旋转位

上图为我们提供了解决方案。如果我们仔细观察 b) 和 c) 点，我们会看到最终结果中出现了落位。该结果可以通过将下降位右移 32-10 = 22 个位置来获得。

因此，如果我们将 n 左移 10 个位置，我们将获得在上图的右侧（如 b 点）或被除数填充零的二进制表示下一个部门）。如果我们 右移 n 22 个位置，我们会得到一个在左侧填充零的二进制表示（作为下一个除数的除数）。此时，OR[|] 运算符进入场景，如下例所示：

图 9.39 – 应用 OR[|] 运算符

左旋转的最终结果是11011111111101111110010001100100。现在，我们可以很容易地将其放入代码中，如下：

public static int leftRotate(int n, int bits) {
  int fallBits = n << bits;
  int fallBitsShiftToRight = n >> (MAX_INT_BITS - bits);
  return fallBits | fallBitsShiftToRight;
}

现在，通过实施正确的轮换来挑战自己。

对于正确的 旋转，代码将如下所示（您应该能够毫无问题地遵循此解决方案）：

public static int rightRotate(int n, int bits) {
  int fallBits = n >> bits;
  int fallBitsShiftToLeft = n << (MAX_INT_BITS - bits);
  return fallBits | fallBitsShiftToLeft;
}

完整的应用程序称为 RotateBits。

Coding challenge 19 – Calculating numbers

问题：考虑两个 位置，i 和 j (j > i)，表示二进制表示中两位的位置。编写一段代码，返回一个 32 位整数 ，在 i（含）和 j（含），其余位为 0（未设置）。

解决方案：让我们考虑 i=3 和 j=7。我们知道所需的 32 位整数是 248，或者，以二进制表示，11111000（或全 0，000000000000000000000000011111000）。

如果你关注Coding challenge 8 – Subtracting binaries on paper那么你应该知道0减1是可以完成的运算从当前位的左侧借位。 borrowing 技术向左传播，直到找到位 1。此外，如果我们记得 1 减 0 是 1，那么我们可以写出以下减法：

图 9.40 – 减法

看看这个减法的结果。 1 正好在 i=3（含）和 j=7（含）之间。这正是我们要寻找的数字：248。被除数和除数是通过左移1获得( j+1) 个位置和 i 个位置。

有了这些 语句，很容易将它们放入代码中：

public static int setBetween(int left, int right) {
  return (1 << (right + 1)) - (1 << left);
}

完整的应用程序称为NumberWithOneInLR。

Coding challenge 20 – Unique elements

亚马逊、谷歌、Adobe、微软，Flipkart

问题：考虑一个给定的整数数组，arr。该数组中的每个元素恰好出现 3 次，除了 一个元素，它只出现一次。这使它独一无二。编写一段 代码，在 O(n) 复杂度时间和 O(1) 额外空间中找到这个唯一元素。

解决方案：假设给定的数组是 arr={4, 4, 3, 1, 7, 7, 7, 1, 1, 4}，所以 3 是唯一元素。如果我们把这些数字写成二进制表示，我们会​​得到： 100, 100, 011, 001, 111, 111, 111, 001, 001, 100。现在，让我们将相同位置的位相加，检查是否结果总和是 3 的倍数，如下所示：

• 第一位的总和 % 3 = 0+0+1+1+1+1+1+1+1+0 = 7 % 3 = 1
• 第二位的总和 % 3 = 0+0+1+0+1+1+1+0+0+0 = 4 % 3 = 1
• 第三位之和 % 3 = 1+1+0+0+1+1+1+0+0+1 = 6 % 3 = 0

唯一编号是 011 = 3。

让我们看另一个例子。这一次，arr={51, 14, 14, 51, 98, 7, 14, 98, 51, 98}，所以 7 是唯一元素。让我们将之前使用的相同逻辑应用于二进制表示：110011, 1110, 1110, 110011, 1100010, 111, 1110, 1100010, 110011, 1100010。这一次，让我们使用图表，因为这会使事情更清楚：

图 9.41 – 查找给定数组中的唯一元素

所以，基于这两个例子，我们可以详细阐述如下算法：

1. 总结 相同位置的位。
2. 对于每个 sum，计算模数 3。
3. 如果 sum % 3 = 0（sum 是 3 的倍数），这意味着该位在元素中设置在给定的元素中出现三次。
4. 如果 sum % 3 ! = 0（sum 不是 3 的倍数），这意味着该位在出现一次的元素中设置（但不是确定该位是否未设置或在出现三次的元素中设置）。
5. 我们必须重复 步骤 1、2 和 3给定元素和位的所有位置。通过执行此操作，我们将获得仅出现一次的元素，正如您在上图中看到的那样。

代码如下：

private static final int INT_SIZE = 32;
public static int unique(int arr[]) {
  int n = arr.length;
  int result = 0;
  int nr;
  int sumBits;
  // iterate through every bit 
  for (int i = 0; i < INT_SIZE; i++) {
    // compute the sum of set bits at 
    // ith position in all array
    sumBits = 0;
    nr = (1 << i);
    for (int j = 0; j < n; j++) {
      if ((arr[j] & nr) == 0) {
        sumBits++;
      }
    }
    // the sum not multiple of 3 are the 
    // bits of the unique number
    if ((sumBits % 3) == 0) {                
      result = result | nr;
    }
  }
  return result;
}

这是解决此问题的一种方法。另一种方法是 XOR[^] 运算符在两次应用于 相同的数字时返回 0。此外，XOR[^] 运算符是关联的（给出结果相同，无论分组：1 ^ 1 ^ 2 ^ 2 = 1 ^ 2 ^ 1 ^ 2 = 0）和可交换（与顺序无关：1 ^ 2 = 2 ^ 1）。但是，如果我们对相同的数字进行三次异或[^]，那么结果将是相同的数字，因此对所有数字使用异或[^] 将没有帮助。但是，我们可以使用以下算法：

使用变量注意该变量是第一次出现。

1. 对于每个新元素，将它的 XOR[^] 放在一个变量中，oneAppearance。
2. 如果元素第二次出现，那么它将从 oneAppearance 中删除，我们将它的 XOR[^] 放在另一个变量中，twoAppearances 。
3. 如果该元素第三次出现，那么它将从 oneAppearance 和 twoAppearances 中删除。 oneAppearance 和 twoAppearances 变量变为 0，我们开始寻找新元素。
4. 对于所有出现 3 次的元素，oneAppearance 和 twoAppearances 变量将为 0。另一方面，对于元素仅出现一次，oneAppearance 变量将设置为 该值。

在代码方面，这看起来 如下：

public static int unique(int arr[]) {
  int oneAppearance = 0;
  int twoAppearances = 0;
  for (int i = 0; i < arr.length; i++) {
    twoAppearances = twoAppearances
        | (oneAppearance & arr[i]);
    oneAppearance = oneAppearance ^ arr[i];
    int neutraliser = ~(oneAppearance & twoAppearances);
    oneAppearance = oneAppearance & neutraliser;
    twoAppearances = twoAppearances & neutraliser;
  }
  return oneAppearance;
}

此代码的运行时间为 O(n)，额外时间为 O(1)。完整的应用程序称为 OnceTwiceThrice。

Coding challenge 21 – Finding duplicates

亚马逊、谷歌、Adobe、微软，Flipkart

问题：假设给定一个整数数组，范围从 1 到 n，其中 n 最多可以是 32,000。该数组可能包含重复项，而您不知道 n 的值。编写一段代码， 仅使用 4 KB 的内存打印给定数组中的所有重复项。

解决方案：解决方案应该从开始，即 4 KB 的内存相当于 4 * 8 * 210 位。由于 4 * 8 * 210 大于 32,000，我们可以创建一个 32,000 位的向量，并将每个整数表示为 1 位。不需要为位向量编写我们自己的实现；我们可以简单地使用 Java 内置的 BitSet 类（这个类实现了一个根据需要增长的位向量）。

使用 BitSet，我们可以迭代给定的数组，并且对于每个遍历的元素，将相应索引中的位从 0 翻转到 1。如果我们尝试翻转一个位，即已经 1，然后我们找到并打印一个副本。代码非常简单：

  private static final int MAX_N = 32000;
  public static void printDuplicates(int[] arr) {
    BitSet bitArr = new BitSet(MAX_N);
    for (int i = 0; i < arr.length; i++) {
      int nr = arr[i];
      if (bitArr.get(nr)) {                
        System.out.println("Duplicate: " + nr);
      } else {
        bitArr.set(nr);
      }
    }
  }

完整的应用程序称为FindDuplicates。

Coding challenge 22 – Two non-repeating elements

亚马逊、谷歌、Adobe

问题：考虑给定一个包含 2n+2 个元素。 2n 元素是重复一次的 n 元素。因此， 2n 中的每个元素在给定的 数组中出现两次。其余两个元素只出现一次。编写一段代码来查找这两个元素。

解决方案：假设给定的数组是 arr={2, 7, 1, 5, 9, 4, 1, 2、5、4}。我们要查找的两个数字是 7 和 9。这两个数字在数组中只出现一次，而 2、1、5 和 4 出现两次。

如果我们考虑蛮力方法，那么迭代数组并检查每个元素的出现次数是非常直观的。但是这个解决方案不会给面试官留下深刻印象，因为它的运行时间是 O(n2)。

另一种方法包括对给定数组进行排序。这样，重复的元素被组合在一起，以便我们可以计算每个组的出现次数。大小为 1 的组表示非重复值。在寻找更好解决方案的过程中提及这种方法是件好事。

更好的解决方案依赖于散列。创建一个地图<元素, 计数>并用元素和出现次数填充它（例如，对于我们的数据，我们将有以下对：（2, 2）， (7, 1), (1, 2), (5, 2), (9, 1) 和 (4, 2))。现在，遍历地图并定位计数为 1 的元素。在寻找更好解决方案的过程中，最好提及这种方法。

在本章中，我们处理的是位，因此最好的解决方案应该依赖于位操作。此解决方案依赖于 XOR[^] 运算符和我们在 提示和技巧 部分中提到的提示：

• 如果我们将一个数与自身异或[^]偶数次，则结果如下 0 (x ^ x = 0; x ^ x ^ x^ x = (x ^ x) ^ ( x ^ x) = 0 ^ 0 = 0)

另一方面，如果我们将 XOR[^] 运算符应用于两个不同的数字 p 和 q，那么结果是一个数字，它包含 p 和 q 不同的地方的位集合（1 的位）。这意味着如果我们对数组中的所有元素应用 XOR[^] (xor = arr[0]^< em class="italic">arr[1]^arr[2] ^ ... ^ arr [arr.length-1])，那么所有重复的元素将相互抵消。

因此，如果我们取 XOR[^] 的结果的任何一个集合位（例如，最右边的位）并将数组的元素分成两组，那么一组将包含具有相同位集合的元素，并且 other set 将包含未设置相同位的元素。换句话说，我们通过比较 XOR[^] 的最右边集合位与每个元素中相同位置的位，将元素分成两个 集合。通过这样做，我们将在一组中获得 p，在另一组中获得 q。

现在，如果我们将 XOR[^] 运算符应用于第一个集合中的所有元素，那么我们将获得第一个非重复元素。在另一组中执行相同操作将获得第二个非重复元素。

让我们将此流程应用于我们的数据，arr={2, 7, 1, 5, 9, 4, 1, 2, 5, 4}。因此，7 和 9 是非重复值。首先，我们将 XOR[^] 运算符应用于所有数字：

xor = 2 ^ 7 ^ 1 ^ 5 ^ 9 ^ 4 ^ 1 ^ 2 ^ 5 ^ 4 = 0010 (2) ^ 0111 (7) ^ 0001 (1) ^ 0101 (5) ^ 1001 (9) ^ 0100 (4) ^ 0001 (1) ^ 0010 (2) ^ 0101 (5) ^ 0100 (4) = 1110 = 7 ^ 9 = 0111 & 1001 = 1110 = 14。

所以，7 ^ 9！ = 0 如果 7 ！ = 9。因此，将有至少一个设置位（至少一位为 1）。我们可以取任何设置的位，但将最右边的位取为 xor & 〜（异或-1）。所以，我们有 1110 & ~(1101) = 1110 & 0010 = 0010。随意采取任何其他设置位。

到目前为止，我们在这两个数字（7 和 9）的 XOR[^] 中找到了这个设置位（0010），所以这个位必须存在于 7 或 9 中（在这种情况下，它存在于 7 中）。接下来，让我们通过比较 XOR[^] 的最右边集合位与每个元素中相同位置的位来将元素分成两组。我们得到第一个集合，包含元素 {2, 7, 2}，第二个集合包含元素 {1, 5, 9, 4, 1, 5, 4}。由于 2、7 和 2 包含设置位，因此它们在第一组中，而 1、5、9、4、1、5 和 4 不包含设置位，这意味着它们是第二组的一部分放。

这样，我们将第一个非重复元素 (7) 隔离在一个集合中，并将第二个非重复元素 (9) 放入另一个集合中。此外，每个重复的元素将在同一组位表示中（例如，{2, 2} 将始终在同一组中）。

最后，我们对每个集合应用 XOR[^]。所以，我们有 xor_first_set = 2 ^ 7 ^ 2 = 010 ^ 111 ^ 010 = 111 = 7（第一个非重复元素）。

对于第二组，我们有：

xor_second_set = 1 ^ 5 ^ 9 ^ 4 ^ 1 ^ 5 ^ 4 = 0001 ^ 0101 ^ 1001 ^ 0100 ^ 0001 ^ 0101 ^ 0100 = 1001 = 9（第二个非重复元素）。

完毕！

在代码方面，我们 有以下内容：

public static void findNonRepeatable(int arr[]) {
  // get the XOR[^] of all elements in the given array
  int xor = arr[0];
  for (int i = 1; i < arr.length; i++) {
    xor ^= arr[i];
  }
  // get the rightmost set bit (you can use any other set bit)
  int setBitNo = xor & ~(xor - 1);
  // divide the elements in two sets by comparing the 
  // rightmost set bit of XOR[^] with the bit at the same 
  // position in each element
  int p = 0;
  int q = 0;
  for (int i = 0; i < arr.length; i++) {
    if ((arr[i] & setBitNo) != 0) {
      // xor of the first set
      p = p ^ arr[i];
    } else {
      // xor of the second set
      q = q ^ arr[i];
    }
  }
  System.out.println("The numbers are: " + p + " and " + q);
}

这段代码的运行时间是O(n)，辅助空间是O(1)（n是从给定的数组）。完整的 应用程序称为TwoNonRepeating。

Coding challenge 23 – Power set of a set

亚马逊、谷歌、Adobe

问题：考虑一个给定集合，S。编写一段代码，返回 S 的幂集。一个幂集 P(S) 是一个集合 S 的集合，它是 S，包括 空集和S 本身。

解决方案：考虑给定的 S 是 {a, b, c }。如果是这样，Power Set 包括 {}, {a}, {b}, {c}, {a, b}, {a, c em>}, {a, c} 和 {a, b, c }。请注意，对于包含三个元素的集合，幂集包含 23=8 个元素。对于包含四个元素的集合，幂集包含 24=16 个元素。一般来说，对于一组 n 元素，幂集包含 2n 个元素。

现在，如果我们生成从 0 到 2n-1 的所有二进制数，那么我们会得到类似下面的结果（这个例子是 23-1）：

20=000, 21=001, 22=010, 23=011, 24=100, 25=101, 26=110, 27=111

接下来，如果我们列出这些 二进制文件，我们认为第一个设置位（最右边的位）是 与 a，第二个设置位关联b，第三个设置位（最左边的位）关联c，然后我们得到以下内容：

20 = 000 = {}

21 = 001 = {a}

22 = 010 = {b}

23 = 011 = {a, b}

24 = 100 = {c}

25 = 101 = {a, c}

26 = 110 = {b, c}

27 = 111 = {a, b, c}

请注意，如果我们将 1 的位替换为 a、b 和 c ，然后我们获得给定集合的幂集。基于这些语句，我们可以为给定的集合创建以下伪代码，S：

Compute the Power Set size as 2 size of S
Iterate via i from 0 to Power Set size
     Iterate via j from 0 to size of S
          If jth bit in i is set then
               Add jth element from set to current subset
     Add the resulted subset to subsets
Return all subsets

所以，这个问题的解决方案可以写成如下：

public static Set<Set<Character>> powerSet(char[] set) {
  // total number of subsets (2^n)
  long subsetsNo = (long) Math.pow(2, set.length);
  // store subsets
  Set<Set<Character>> subsets = new HashSet<>();
  // generate each subset one by one
  for (int i = 0; i < subsetsNo; i++) {
    Set<Character> subset = new HashSet<>();
    // check every bit of i
    for (int j = 0; j < set.length; j++) {
      // if j'th bit of i is set, 
      // add set[j] to the current subset
      if ((i & (1 << j)) != 0) {                    
        subset.add(set[j]);
      }
    }
    subsets.add(subset);
  }
  return subsets;
}

完整的代码是，称为PowerSetOfSet。

Coding challenge 24 – Finding the position of the only set bit

Adobe、微软

问题：考虑一个正整数n。此数字的二进制表示具有单个位集（单个位 1）。编写一段代码，返回该位的位置。

解决方案：问题本身给了我们一个重要的细节或约束：给定的数字包含一位 1。这意味着给定的数字必须是 2 的幂。只有 20 , 21, 22, 23, 24, 25, ..., 2n 具有包含单个位 1 的二进制表示。所有其他数字包含 0 或多个 1 值。

一个 n & (n-1) 公式可以告诉我们给定的数字是否是 2 的幂。查看下图：

图 9.42 – n & (n-1) 公式给了我们两个的幂

所以，数字 0, 1, 2, 8, 16, ... 的二进制表示为 n & (n-1) 为 0000。到目前为止，我们可以说给定的数字是 2 的幂。如果不是，那么我们可以返回 -1，因为没有位 1 或者有多个位 1。

接下来，我们可以将 n 向右移动，只要 n 不为 0，同时跟踪移位次数。当 n 为 0 时，这意味着 我们已经移动了 1 的一位，所以我们可以停止并返回 计数的班次。基于这些陈述，此代码非常简单：

public static int findPosition(int n) {
  int count = 0;
  if (!isPowerOfTwo(n)) {
    return -1;
  }
  while (n != 0) {
    n = n >> 1;
    ++count;
  }
  return count;
}
private static boolean isPowerOfTwo(int n) {
  return (n > 0) && ((n & (n - 1)) == 0);
}

完整的代码称为PositionOfFirstBitOfOne。

Coding challenge 25 – Converting a float into binary and vice versa

问题：考虑一个 Java float 数字，n。编写一段代码，将此 float 转换为 IEEE 754 单精度二进制浮点 (binary-32) 和反之亦然。

解决方案：要解决这个问题，重要的是要知道Java使用IEEE 754单精度二进制浮点表示浮点数 数字。 IEEE 754 标准将二进制 32 指定为具有符号位（1 位）、指数宽度（8 位可以表示 256 个值）和有效精度（24 位（23 位显式存储）），也称为尾数。

下图表示 IEEE 754 标准中的二进制 32：

图 9.43 – IEEE 754 单精度二进制浮点（二进制 32）

float 值，当由具有给定符号、有偏指数、e 的 32 位二进制数据表示时，（8位无符号整数）和一个 23 位小数，如下所示：

图 9.44 – 浮点值

存储在 8 位上的指数使用 0 到 127 的值来表示负指数（例如 2-3），使用 128-255 的值表示正指数。负指数 10-7 的值为 -7+127=120。 127 的值称为指数偏差。

有了这些信息，您应该能够将 float 数字转换为 IEEE 754 二进制 32 表示，反之亦然。在检查名为 FloatToBinaryAndBack 的源代码之前，请尝试使用您自己的实现。

这是本章的最后一个编码挑战。让我们快速总结一下！

由于本章是位操作的综合资源，那么如果您能做到这一点，那么您已经大大提高了您的位操作技能。我们涵盖了主要的理论方面并解决了 25 个编码挑战，以帮助您学习解决位操作问题的模式和模板。

在下一章中，我们将继续我们的数组和字符串之旅。