Peasant or binary multiplication

Peasant or binary multiplication has been widely used among those who are unschooled and thus have not memorized the multiplication tables required by long multiplication. The algorithm was also in use in ancient Egypt [Wiki]. :)

Explain:
suppose,
the task is to find the value of 12 x 7



mathematically, we know
12 x 7 = 7 x 12
        = 7 x (8 + 4)
        = 7 x (8 + 4 + 0 +0 )
        = 7 x (1x2^3+1x2^2+0x2^1+0x2^0)
        = 7 x 2^3 + 7 x 2^2 + 0x2^1 + 0x2^0)
        = 7 < < 3 + 7 < < 2 + 0 + 0
a = (1100)2  b = 7 (111)2
a                                b                             r =0
--                             -----                       -----------
1100                          111                         r = r+0x7
110 (RHS)                   1110 (LHS)                r = r+0x14
11(RHS)                    11100 (LHS)                r = r+1x28 = 28
1 (RHS)                   111000 (LHS)                r = r + 1x56=84
0 break

Result: 12 x 7 = 84

A more complicated example, using the figures from the earlier examples (23,958,233 and 5,830):

Decimal:             Binary:
5830  23958233       1011011000110  1011011011001001011011001
2915  47916466       101101100011  10110110110010010110110010
1457  95832932       10110110001  101101101100100101101100100
728  191665864       1011011000  1011011011001001011011001000
364  383331728       101101100  10110110110010010110110010000
182  766663456       10110110  101101101100100101101100100000
91  1533326912       1011011  1011011011001001011011001000000
45  3066653824       101101  10110110110010010110110010000000
22  6133307648       10110  101101101100100101101100100000000
11 12266615296       1011  1011011011001001011011001000000000
5  24533230592       101  10110110110010010110110010000000000
2  49066461184       10  101101101100100101101100100000000000
1  98132922368       1  1011011011001001011011001000000000000
  ————————————          1022143253354344244353353243222210110 (before carry)
  139676498390         10000010000101010111100011100111010110 

[Wiki]


code:
--------

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include <stdio.h> typedef long long ll; ll mult(ll a, ll b){ ll r=0; while(a>0){ if (a&1)r+=b; a = a>>1; b = b<<1; } return r; } int main() { ll a,b; scanf ("%lld %lld",&a,&b); printf("\t%lld x %lld: %lld\n",a,b,mult(a,b)); /*Verification*/ printf("\nVerification: \n\n\t%lld x %lld: %lld\n",a,b,a*b); return 0; }

Output:
23958 5830
        23958 x 5830: 139675140

Verification:

        23958 x 5830: 139675140