C语言中实现将Y的二进制位插入X的最后置位后并转换为十进制的代码求助

Problem Description #

I need to write code that takes two integers X and Y, converts them to binary, inserts all bits of Y right after the last set bit (1) of X, then converts the merged binary string back to decimal.

For example:

• Input: X=10 (binary 1010), Y=14 (binary 1110)
• Output: 188 (binary 10111100)
• Explanation: Insert 1110 right after the last set bit of 1010 (which is the rightmost '1'), resulting in 101 + 1110 + 0 = 10111100.

I've written part of the code to convert integers to binary strings, but I'm stuck on merging the binary strings correctly and converting the result back to decimal. Here's my current code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int insertBits(int X, int Y) {
    int int_to_bin(int k) {
        return (k == 0 || k == 1? k : ((k % 2) + 10 * int_to_bin(k / 2)));
    }
    int a1 = int_to_bin(X);
    int a2 = int_to_bin(Y);
    char msg[20];
    char msg1[20];
    char deal[20];
    sprintf(msg, "%d", a1);
    sprintf(msg1, "%d", a2);
    int k = 0;
    int i = 0;
    for (i = strlen(msg) - 1; i >= 0; i--) {
        if (msg[i] == '1') {
            k = 1;
            break;
        }
    }
    memcpy(msg, &msg[0], i);
    memcpy(deal, &msg[i], -1);
    strcat(msg, deal);
    printf("%s", strcat(deal, msg1));
}
int main() {
    insertBits(10, 20);
}

Issues with Current Approach #

Your current method has two critical flaws:

1. Overflow Risk: Converting binary representations to integers works for small numbers, but for larger values (e.g., numbers with binary strings longer than 10 digits), the integer will overflow the int type and produce incorrect results.
2. Unsafe String Manipulation: Your memcpy calls use invalid parameters (like -1 for length), which leads to undefined behavior. Merging strings this way is error-prone and unnecessary.

Better Solution: Bitwise Operations #

We can achieve the desired result efficiently and safely using bitwise operations, no string manipulation required. Here's the step-by-step logic:

1. Count trailing zeros in X: Find how many zeros are at the end of X's binary form (call this t). This tells us the position of the last set bit relative to the end.
   • For X=10 (1010), t=1 (one trailing zero).
2. Count bits in Y: Determine how many bits are needed to represent Y (call this y_bits).
   • For Y=14 (1110), y_bits=4.
3. Shift X to make space: Right-shift X by t bits to remove trailing zeros, then left-shift the result by t + y_bits bits to make room for Y.
   • X=10 → 10 >> 1 = 5 → 5 << (1+4) = 160 (10100000).
4. Shift Y to align: Left-shift Y by t bits to place it right after X's last set bit.
   • Y=14 → 14 << 1 = 28 (11100).
5. Combine values: Add the shifted X and shifted Y to get the final result.
   • 160 + 28 = 188 (10111100), which matches the example.

Complete Working Code #

#include <stdio.h>

int countTrailingZeros(int num) {
    if (num == 0) return 0;
    int count = 0;
    while ((num & 1) == 0) {
        count++;
        num >>= 1;
    }
    return count;
}

int countBits(int num) {
    if (num == 0) return 0;
    int count = 0;
    while (num > 0) {
        count++;
        num >>= 1;
    }
    return count;
}

int insertBits(int X, int Y) {
    if (Y == 0) return X; // No bits to insert if Y is 0
    
    int trailing_zeros = countTrailingZeros(X);
    int y_bit_count = countBits(Y);
    
    int shifted_X = (X >> trailing_zeros) << (trailing_zeros + y_bit_count);
    int shifted_Y = Y << trailing_zeros;
    
    return shifted_X + shifted_Y;
}

int main() {
    // Test the example case
    int result = insertBits(10, 14);
    printf("Example result: %d\n", result); // Outputs 188
    
    // Test another case: X=20 (10100), Y=20 (10100)
    // Expected output: 720 (binary 1011010000)
    result = insertBits(20, 20);
    printf("Additional test result: %d\n", result); // Outputs 720
    
    return 0;
}

Helper Function Explanations #

• countTrailingZeros: Iterates through the least significant bits to count consecutive trailing zeros in the input number.
• countBits: Counts the number of bits required to represent the input number by right-shifting until the number becomes zero.

This approach is faster, avoids overflow risks, and eliminates the complexity of string manipulation.

内容的提问来源于stack exchange，提问作者Heisenberg