给定一个以字符串形式表示的二进制数 s。我们的任务是返回其 1‘s补码 和 2‘s补码,形式为 [onesComplement, twosComplement] 的数组。
通过翻转所有位即可获得二进制数的 1‘s补码。0 变为 1,而 1 变为 0。正数保持不变,而负数通过取其正对应数的 1‘s补码来表示。
例如,在 8位表示法 中:
- +9 表示为 00001001。
- -9 表示为 11110110,这是 00001001 的 1‘s补码。
示例:
> 输入: s = "0111"
> 输出: 1000
> 解释: 每一位都被翻转了,即 0 变为 1,1 变为 0。
>
> 输入: s= "1100"
> 输出: 0011
> 解释: 每一位都被翻转了,即 0 变为 1,1 变为 0。
通过先找到 1‘s补码(翻转所有位),然后对结果加 1,即可获得二进制数的 2‘s补码。在 2‘s补码表示法中,最高有效位 (MSB) 代表符号位。0 表示正数,而 1 表示负数。其余位代表数值大小。
正数的表示方式与 1‘s补码和符号位表示法相同。负数通过取其正对应数的 2‘s补码获得。
示例:
> 输入: s = "0111"
> 输出: 1001
> 解释: 找到 1‘s补码 -> 1000,然后加 1 -> 1000 + 1 = 1001
>
> 输入: "1100"
> 输出: 0100
> 解释: 找到 1‘s补码 -> 0011,然后加 1 -> 0011 + 1 = 0100
> 这个思路是首先通过翻转二进制字符串的每一位来计算 1‘s补码。然后,为了找到 2‘s补码,我们从最右边的位开始,给 1‘s补码 加 1。如果所有位都翻转了(导致溢出),则在开头添加一个额外的 ‘1‘。这确保了有符号二进制数的正确表示。
实现上述思路的步骤:
- onesComplement() 遍历 s 并将每个 ‘0‘ 翻转为 ‘1‘,将 ‘1‘ 翻转为 ‘0‘。
- twosComplement() 调用 onesComplement,然后将 1 加到最低有效位上。
- 从右到左遍历 s,将 ‘1‘ 翻转为 ‘0‘,直到遇到第一个 ‘0‘,将其变为 ‘1‘。
- 如果没有找到 ‘0‘,则在 s 的前面加上 ‘1‘,以维持正确的 2‘s补码表示。
C++
CODEBLOCK_d15ed676
Java
“
// Java program to find 1‘s and 2‘s
// complement of a binary number
import java.util.*;
class GfG {
// Function to find 1‘s complement
static String onesComplement(String s) {
// Traverse each bit and flip it
StringBuilder result = new StringBuilder(s);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ‘0‘) {
result.setCharAt(i, ‘1‘);
} else {