I wasn’t sure whether to post this one or not. More over, my dilemma was whether to document this one or not. I decided that it’s so hard to explain what’s going on, that I will only dump my code here. The interface is ugly, because you cannot divide by zero…<\/p>\n
\/\/ return success, *ret = a \/ b
\nint div(unsigned short a, unsigned short b, unsigned short *ret)
\n{
\n\u00a0if (b == 0) return 0;
\n\u00a0*ret = 0;
\n\u00a0unsigned short mask = 0, len = 0;<\/p>\n
\u00a0\/\/ calc the mask of b.
\n\u00a0for (int i = 15; i >= 0; i–) {
\n\u00a0 if (b & (1 << i)) {
\n\u00a0 mask = (1 << i) – 1;
\n\u00a0 len = 16 – i;
\n\u00a0 break;
\n\u00a0 }
\n\u00a0}
\n\u00a0\/\/ complement mask.
\n\u00a0mask = ~mask;<\/p>\n
\u00a0\/\/ left justify b.
\n\u00a0while ((~b) & (1 << 15)) b <<= 1;<\/p>\n
\u00a0while (len–) {
\n\u00a0 *ret <<= 1;
\n\u00a0 if ((a & mask) >= b) {
\n\u00a0\u00a0 *ret |= 1;
\n\u00a0\u00a0 a -= b;
\n\u00a0 }
\n\u00a0 b >>= 1;
\n\u00a0 mask >>= 1;
\n\u00a0}<\/p>\n
\u00a0return 1;
\n}<\/p>\n
And yes it’s 16 bits division, it will apply for 32 or 64 bits as well. It really was one of the toughest things to write from scratch. Division is not that trivial like subtraction or multiplication. The trick eventually was to use the fact that we’re dealing with binary division..oh well, I quit. Get someone else to describe this one. Although I think there are many ways to implement this one. I remember a friend telling me he didn’t expect this way of solution. I don’t think, however, that this technique may be used for long division for bit array or really big numbers, maybe there’s something faster.<\/p>\n
By the way, this is an unsigned<\/em> division. As far as I know, and I might be wrong, you can’t do signed division without using unsigned division. And to do signed division you just remember the sign of a and b and then make them absolute and then you change the result accordingly. Anyways, if I’m wrong with my assumption, let me know otherwise.<\/p>\n","protected":false},"excerpt":{"rendered":" I wasn’t sure whether to post this one or not. More over, my dilemma was whether to document this one or not. I decided that it’s so hard to explain what’s going on, that I will only dump my code here. The interface is ugly, because you cannot divide by zero… \/\/ return success, *ret […]<\/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-S","_links":{"self":[{"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=\/wp\/v2\/posts\/54"}],"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=54"}],"version-history":[{"count":0,"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=\/wp\/v2\/posts\/54\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=54"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=54"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ragestorm.net\/blogs\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=54"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}