Booth's Algorithm Step by Step

Booth.cc

#include <iostream>
using namespace std;
using uint = unsigned int;
constexpr uint kLength = 6;
constexpr uint kHighBit = 1 << (kLength - 1);
constexpr uint kTrim = ((1 << (kLength)) - 1);

inline void print_binary(uint v) {
  for (uint i = 1 << (kLength - 1); i != 0; i >>= 1) {
    cout << ((v & i) ? 1 : 0);
  }
}

inline uint neg(uint v) {
  return ((~v) & kTrim) + 1;
}

inline void shift(uint &h, uint &a, uint &low) {
  low = a & 1;
  a = (a >> 1) | ((h & 1) << (kLength - 1));
  h = (h >> 1) | (h & kHighBit);
}

inline void show_operation(uint a, uint q, uint l, string reason) {
  print_binary(a);
  cout << '\t';
  print_binary(q);
  cout << '\t';
  cout << (l ? 1 : 0);
  cout << '\t';
  cout << reason;
  cout << endl;
}

uint booth(uint q, uint m) {
  uint a = 0;
  uint l = 0;
  show_operation(a, q, l, "Initialization");

  for (uint i = 0; i < kLength; ++i) {
    if ((q & 1) != l) {
      if (q & 1) {
        // 10 -> minus
        a += neg(m);
        a &= kTrim;
        show_operation(a, q, l, "A = A - M");
      } else {
        // 01 -> minus
        a += m;
        a &= kTrim;
        show_operation(a, q, l, "A = A + M");
      }
    }

    shift(a, q, l);
    show_operation(a, q, l, "Shift");
  }

  return (a << kLength) | q;
}

void demo_booth(uint q, uint m) {
  cout << "Q = " << q << "(0b"; print_binary(q); cout << ")" << endl;
  cout << "M = " << m << "(0b"; print_binary(m); cout << ")" << endl;
  cout << "-M = " << "(0b"; print_binary(neg(m)); cout << ")" << endl;
  cout << endl << "Operation:" << endl;
  uint r = booth(q, m);
  cout << endl;
  cout << "Booth's Algorithm = " << r << endl;
  cout << "CPU               = " << q * m << endl;
}

int main(int argc, char **argv) {
  if (argc != 3) {
    cerr << "Usage: " << argv[0] << " A Q" << endl;
    cerr << "Example: " << argv[0] << " 23 19" << endl;
    return -1;
  }

  int a, b;
  sscanf(argv[1], "%d", &a);
  sscanf(argv[2], "%d", &b);
  demo_booth(a, b);
  return 0;
}