A few years a go a friend challenged me to write the basic\u00a0arithmetic operations, add\/sub, div\/mul.\u00a0But the catch was to write them without using that same instruction for doing the calculation and to make it as a\u00a0long multiplication rather than log(A*B). I think the Multiply implementation is the easiest one amongst these operations, so I decided to start with it:<\/p>\n
unsigned int mul(unsigned int a, unsigned int b)
\n{
\n\u00a0 unsigned int sum = 0, d = 0;
\n\u00a0 while (a) {
\n\u00a0\u00a0\u00a0\u00a0 if (a & 1) sum += (b << d);
\n\u00a0\u00a0 \u00a0 a >>= 1;
\n\u00a0\u00a0 \u00a0 d++;
\n\u00a0 }
\n\u00a0 return sum;
\n}<\/p>\n
The idea of the algorithm, which I wrote from scratch, was to treat the input A as a mask. And anytime the next bit is set in the mask, I accumulate\u00a0the shifted B. So what you get actually is\u00a0long multiplication, which will work for negative numbers as well as positive ones, since the nature of 2’s complement numbers.<\/p>\n
You should take a\u00a0paper and a pencil and start playing with the algorithm by\u00a0applying it on small numbers and\u00a0learn how it works… :) Though this one is easy, really.<\/p>\n","protected":false},"excerpt":{"rendered":"
A few years a go a friend challenged me to write the basic\u00a0arithmetic operations, add\/sub, div\/mul.\u00a0But the catch was to write them without using that same instruction for doing the calculation and to make it as a\u00a0long multiplication rather than log(A*B). I think the Multiply implementation is the easiest one amongst these operations, so I […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","jetpack_publicize_message":""},"categories":[21],"tags":[],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/pbWKd-f","_links":{"self":[{"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=\/wp\/v2\/posts\/15"}],"collection":[{"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=15"}],"version-history":[{"count":0,"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=\/wp\/v2\/posts\/15\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=15"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=15"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=15"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}