📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
123
返回列表 发新帖
楼主: Imbalism
跳转到指定楼层
上一主题 下一主题
收起左侧

Facebook: 实现除法运算

🔗
ziegfeld 2011-10-28 09:14:49 | 只看该作者
全局:
回复 20# danielgao


   呵呵~不过说起来是个好想法,脑筋急转弯了~
回复

使用道具 举报

🔗
sprime 2011-10-28 22:07:18 | 只看该作者
全局:
回复 14# danielgao


   有点意思
回复

使用道具 举报

🔗
chen806 2011-10-29 18:38:56 | 只看该作者
全局:
就是移位试商吧?
回复

使用道具 举报

🔗
bosshugoboss 2011-12-17 07:35:46 | 只看该作者
全局:
哈哈哈 这道题有意思!~
回复

使用道具 举报

🔗
wwwyhx 2012-2-18 07:44:16 | 只看该作者
全局:
今天写了一个更新:

int divide(int a, int b) {
        assert(b != 0);

        bool bNeg = false;
        if ((a < 0 && b > 0) || (a > 0 && b < 0))
                bNeg = true;

        unsigned int ua = a < 0 ? -a : a;
        unsigned int ub = b < 0 ? -b : b;

        int msb = 0;
        while ((ub << msb) < ua) msb++;

        int q = 0;
        for (int i = msb; i >= 0; i--) {  //msb is the first bit make (b << mst) > a.
                if ((ub << i) > ua) {
                        continue;
                }
                q |= (1 << i);
                ua -= (ub << i);
        }

        return bNeg ? -q : q;
}

把int转换成unsigned int避免了死循环和溢出, 看看有没有bug吧. 是位除
回复

使用道具 举报

🔗
wwwyhx 2012-2-19 06:17:24 | 只看该作者
全局:
再贴一种解法(正常解法):

  1. int divide2(int a, int b)
  2. {
  3.         assert(b != 0);

  4.         bool bNeg = false;
  5.         if ((a < 0 && b > 0) || (a > 0 && b < 0))
  6.                 bNeg = true;

  7.         unsigned int ua = (a < 0) ? -a : a;
  8.         unsigned int ub = (b < 0) ? -b : b;

  9.         int nIter = 0;
  10.         for (int i = 0; i < 32; i++)
  11.         {
  12.                 if (((1 << i) & ub) != 0)
  13.                         nIter = i;
  14.         }

  15.         unsigned int uRes = 0;
  16.         for (int i = 31 - nIter; i >= 0; i--)
  17.         {
  18.                 if ((ub << i) <= ua)
  19.                 {
  20.                         uRes += (1 << i);
  21.                         ua -= (b << i);
  22.                 }
  23.         }

  24.         return bNeg ? -uRes : uRes;
  25. }
复制代码
回复

使用道具 举报

🔗
diamrem 2012-2-24 12:04:36 | 只看该作者
全局:
按照Sanjoy的那本书上的讲解写了一种解法,没处理negative和divider是0的情况


  1. typedef struct{
  2.     int q,r;
  3. }result;

  4. result divide2(int a, int b){
  5.     printf("%d\n",a);
  6.     result re = {0, 0};
  7.     if (a == 0){
  8.         return re; //Basic condition
  9.     } else{
  10.         re = divide2(a>>1, b);
  11.         printf("%d, %d\n", re.q, re.r);
  12.         //Multiply 2 to the result previous recursion
  13.         re.q = re.q << 1;
  14.         re.r = re.r << 1;
  15.         //If a is odd, plus 1 to remainder
  16.         if ((a&1) != 0){
  17.             re.r += 1;
  18.         }
  19.         //If remainder is greater than b, subtract if from r and add 1 to quotient
  20.         if (re.r >= b){
  21.             re.r = re.r - b;
  22.             re.q = re.q + 1;
  23.         }                                                                                                                                 
  24.         return re;
  25.     }
  26. }
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表