จำนวนขั้นตอนสูงสุดในการแปลง 0 เป็น X ด้วย Bitwise AND ใน C++

โจทย์ปัญหา

ได้รับจำนวนเต็ม X ให้หาจำนวนขั้นตอนสูงสุดในการแปลงจาก 0 ไปเป็น X โดยแต่ละขั้นตอนต้องแปลงจาก A ไป B โดยที่ A != B และ A & B = A (Bitwise AND)

ตัวอย่าง

นำเข้า: X = 7
ผลลัพธ์: 3
ขั้นตอน:

• ขั้นตอน 1: 0 (000) → 1 (001) | 0≠1 และ 0&1=0
• ขั้นตอน 2: 1 (001) → 3 (011) | 1≠3 และ 1&3=1
• ขั้นตอน 3: 3 (011) → 7 (111) | 3≠7 และ 3&7=3

แนวคิดการแก้ปัญหา

สังเกตว่าเงื่อนไข A & B = A หมายถึง บิตที่เป็น 1 ใน A ต้องเป็น 1 ใน B ด้วย (แต่ B อาจมีบิต 1 เพิ่มเติมได้)

ดังนั้น การแปลงจาก 0 ไป X อย่างมีขั้นตอนมากที่สุด คือการตั้งค่าบิต 1 ทีละบิต ตามลำดับจาก LSB ไป MSB จำนวนขั้นตอนสูงสุดจึงเท่ากับ จำนวนบิต 1 (Set bits) ใน X

โค้ดตัวอย่าง (C++)

#include <bits/stdc++.h>
using namespace std;

int maxTransformation(int x) {
    int steps = 0;
    // นับจำนวนบิต 1
    while (x) {
        steps += x & 1;
        x >>= 1;
    }
    return steps;
}

int main() {
    int x = 7;
    cout << "The maximum number of steps to transform 0 to "
         << x << " with bitwise AND are " << maxTransformation(x);
    return 0;
}

ผลลัพธ์

The maximum number of steps to transform 0 to 7 with bitwise AND are 3

คำอธิบายเพิ่มเติม

• ขั้นตอนน้อยที่สุดคือ 1 ขั้นตอน (แปลง 0 → X โดยตรง เพราะ 0 ไม่มีบิต 1 ใดๆ)
• ขั้นตอนมากที่สุด = จำนวน Set bits ใน X
• สามารถใช้ built-in function __builtin_popcount(x) ใน GCC/Clang ได้