今天去笔试 忘记了 2圆位置关系还有内含和内切 .做错了5555555555

biosxjj

判断2圆 相交..  我只判断了是否 相离  而且我把外切也当成相交的特殊情况 郁闷 ....初中的数学忘记了 ...........

还有题不会做   a=b/13 怎么只用c语言的位操作  表示

biinn

Post by biosxjj

还有题不会做   a=b/13 怎么只用c语言的位操作  表示

这好像是一道很经典的面试题。

2. b/13 = b/16 + [(b/16)x3]/13
3.      = b/16 + B/13      /* B = (b/16)x3 */            
5. int div13 (int var)
6. {
7.     int tmp1, tmp2, ret = 0;
9.     for ( ; var >= 13; var = tmp1+tmp1+tmp1+tmp2)
10.     {
11.          tmp1 = var >> 4;                /* var / 16 */
12.          tmp2 = var - (tmp1 << 4);  /* var % 16 */
14.          if (var < 16)
15.               return ret += 1;
17.          ret += tmp1;
18.     }
20.     return ret;
21. }

复制代码

DoDo

感谢 biinn 兄提供这个算法. 虽然能理解

1. 
   
2. b/13 = b/16 + [(b/16)x3]/13
   
3.      = b/16 + B/13      /* B = (b/16)x3 */
   

复制代码

但还是不太理解具体的算法实现, biinn 兄能为在下这类数学不好的兄弟们补习一下么, 呵呵

P.S. /* var % 16 */ 不妨用

1. tmp2 = var & 0x0F;

复制代码

来实现, 应该会比减法快

biinn

Post by DoDo
P.S. /* var % 16 */ 不妨用
tmp2 = var & 0x0F;
来实现, 应该会比减法快

谢谢指点，这个是最快的！谢谢

Post by DoDo

b/13 = b/16 + [(b/16)x3]/13
     = b/16 + B/13      /* B = (b/16)x3 */
但还是不太理解具体的算法实现

我试试看能不能说清楚：
离13最近的2的幂（这么说对吗？）是16，先把b分成16份。
b/13 = 一份 + 剩下的三份再除以13。
问题就变成了三份 b/16 除以13的问题了，循环计算直到这三份小于13.

注意：剩余部分不仅是3x(b/16)，还要加上b%16, 就是上面那个tmp2 = var & 0x0F，呵呵。

DoDo

哦, 有点明白了, 试着把 biinn 兄的算法写成了这个递归算法, 理解起来就容易多了

1. 
   
2. int div13(int x)
   
3. {
   
4.         if (x < 13) return 0;
   
5.         if (!(x >> 4)) return 1;
   
6.         int t = x & 0x0F;
   
7.         x >>= 4;
   
8.         return x + div13((x << 1) + x + t);
   
9. }
   

复制代码

DoDo

Post by biinn
谢谢指点，这个是最快的！谢谢


我试试看能不能说清楚：
离13最近的2的幂（这么说对吗？）是16，先把b分成16份。
b/13 = 一份 + 剩下的三份再除以13。
问题就变成了三份 b/16 除以13的问题了，循环计算直到这三份小于13.

注意：剩余部分不仅是3x(b/16)，还要加上b%16, 就是上面那个tmp2 = var & 0x0F，呵呵。

没想到这么快就有回复, 嗯, 自己跟着程序跑了几遍, 又推导了一会, 终于明白了, 感谢 biinn 兄

biosxjj

受用了 我理解错了 以后只能用  位操作 原来还可以用+-

biosxjj

楼上的都是牛人 ...不过  其实就是递归 b/13=b/16+B/13;
B=b/16*3
但是 为什么B要加上余数 啊  而余数不*3啊~~

biosxjj

不懂阿 ...不懂   比如 24/16=1.5  
1.5*3=4.5  int 为4
但是 24/16=1....8
1*3+8=11
...取整的定律是怎么的阿

DoDo

这里的问题在于 / 代表的是整除.

我们按照 biinn 兄的解释方法来思考这个问题

首先把 b 分成 16 份, 设每一份为 d, 而且在不整除的情况下, 还有一个余数 m

把这 16 个 d 和一个 m 分成两堆
(13d)  +  (3d + m)
对这两堆再分别进行除 13 的操作,

那么第一堆可以整除, 结果为 d, 也就是结果表达式中的 (b/16) 部分;

第二堆如果 (3d+m) 已经小于 13, 那么按照 / 的规则, 它 / 13 的结果为 0, 计算结束, 否则递归操作. 这便是 (b/16*3)/13 部分