11294774 - 二进制加法

题目链接: https://www.nowcoder.com/practice/c0f180f181b04e2990085c2e33c15ad9

题意

给定一个二进制整数 A，找最小的非负二进制整数 B，使得 A + B 是 2 的非负整数幂次。

思路

要使 A + B = 2^k（k ≥ 0），且 B 最小，则需要找最小的 2^k ≥ A，令 B = 2^k - A。

分析 A 的情况：

1. A = 0：最小的 2 的幂是 2^0 = 1，所以 B = 1。
2. A 是 2 的幂次（二进制表示为 1 后跟若干个 0）：B = 0，因为 A 本身已是幂次。
3. 其他情况：设 A 有 n 位（最高位为 1），则 2^(n-1) ≤ A < 2^n，最近的更大幂次是 2^n。

- B = 2^n - A

计算 2^n - A（大数减法）：

利用二进制补码原理：2^n - A = (~A) + 1（对 A 的 n 位取反，再加 1）。

• 将 A 的每一位取反（0→1，1→0），得到 flipped
• flipped + 1 即为所求 B
• 去掉前导零后输出

正确性说明：

• A 以 1 开头（非零），取反后最高位为 0，加 1 不会产生进位到 n+1 位（因为 flipped < 2^(n-1)），结果仍在 n 位内
• 去掉前导零得到 B 的最简二进制表示

复杂度

• 时间：O(n)
• 空间：O(n)

代码

C++

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string A;
    cin >> A;
    int n = A.size();

    // 特殊情况：A = "0"，B = 1（0 + 1 = 1 = 2^0）
    if (A == "0") {
        cout << "1" << endl;
        return 0;
    }

    // 判断 A 是否已是 2 的幂次
    bool isPow2 = true;
    for (int i = 1; i < n; i++) {
        if (A[i] == '1') {
            isPow2 = false;
            break;
        }
    }

    if (isPow2) {
        cout << "0" << endl;
        return 0;
    }

    // B = 2^n - A = (~A) + 1
    string flipped = A;
    for (char& c : flipped) {
        c = (c == '0') ? '1' : '0';
    }

    int carry = 1;
    for (int i = n - 1; i >= 0 && carry; i--) {
        int sum = (flipped[i] - '0') + carry;
        flipped[i] = '0' + (sum % 2);
        carry = sum / 2;
    }

    // 去前导零
    int start = 0;
    while (start < (int)flipped.size() - 1 && flipped[start] == '0') {
        start++;
    }

    cout << flipped.substr(start) << endl;
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String A = br.readLine().trim();
        int n = A.length();

        if (A.equals("0")) {
            System.out.println("1");
            return;
        }

        boolean isPow2 = true;
        for (int i = 1; i < n; i++) {
            if (A.charAt(i) == '1') {
                isPow2 = false;
                break;
            }
        }

        if (isPow2) {
            System.out.println("0");
            return;
        }

        char[] flipped = A.toCharArray();
        for (int i = 0; i < n; i++) {
            flipped[i] = (flipped[i] == '0') ? '1' : '0';
        }

        int carry = 1;
        for (int i = n - 1; i >= 0 && carry > 0; i--) {
            int sum = (flipped[i] - '0') + carry;
            flipped[i] = (char)('0' + sum % 2);
            carry = sum / 2;
        }

        int start = 0;
        while (start < n - 1 && flipped[start] == '0') {
            start++;
        }

        System.out.println(new String(flipped, start, n - start));
    }
}

示例验证