Nhân hai số dùng toán tử bitwise trong C++

Nhân a × b chỉ dùng dịch bit (<<, >>) và cộng. Dựa trên:

• Nếu b chẵn: a × b = (a×2) × (b/2)
• Nếu b lẻ: a × b = (a×2) × (b/2) + a

Thuật toán (Russian Peasant Multiplication)

• result = 0
• Khi b > 0:
  • Nếu b & 1 (lẻ) → result += a
  • a <<= 1 (nhân 2)
  • b >>= 1 (chia 2)

Triển khai C++

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

int multiplyBitwise(int a, int b) {
    int result = 0;
    while (b > 0) {
        if (b & 1) result += a;
        a <<= 1;
        b >>= 1;
    }
    return result;
}

int main() {
    cout << multiplyBitwise(75, 4) << endl;  // 300
    cout << multiplyBitwise(90, 9) << endl;  // 810
    cout << multiplyBitwise(83, 66) << endl; // 5478
    return 0;
}

Kết quả

300
810
5478

Độ phức tạp: O(log b) — nhanh hơn nhân lặp đơn thuần.