当前位置：首页 → 问答吧 → 今天去笔试忘记了 2圆位置关系还有内含和内切 .做错了5555555555

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

时间：2007-03-25

来源：互联网

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

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

作者: biosxjj 发布时间: 2007-03-25

引用:

作者: biosxjj

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

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

代码:

b/13 = b/16 + [(b/16)x3]/13
 = b/16 + B/13 /* B = (b/16)x3 */ 

int div13 (int var)
{
 int tmp1, tmp2, ret = 0;

 for ( ; var >= 13; var = tmp1+tmp1+tmp1+tmp2)
 {
 tmp1 = var >> 4; /* var / 16 */
 tmp2 = var - (tmp1 << 4); /* var % 16 */

 if (var < 16)
 return ret += 1;

 ret += tmp1;
 }

 return ret;
}

作者: biinn 发布时间: 2007-03-26

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

代码:

b/13 = b/16 + [(b/16)x3]/13
 = b/16 + B/13 /* B = (b/16)x3 */

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

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

代码:

tmp2 = var & 0x0F;

来实现, 应该会比减法快

作者: DoDo 发布时间: 2007-03-26

引用:

作者: DoDo

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

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

引用:

作者: 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，呵呵。

作者: biinn 发布时间: 2007-03-26

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

代码:

int div13(int x)
{
        if (x < 13) return 0;
        if (!(x >> 4)) return 1;
        int t = x & 0x0F;
        x >>= 4;
        return x + div13((x << 1) + x + t);
}

作者: DoDo 发布时间: 2007-03-26

引用:

作者: biinn

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

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

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

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

作者: DoDo 发布时间: 2007-03-26

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

作者: biosxjj 发布时间: 2007-03-26

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

作者: biosxjj 发布时间: 2007-03-26

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

作者: biosxjj 发布时间: 2007-03-26

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

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

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

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

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

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

作者: DoDo 发布时间: 2007-03-26

哦我懂了 ...谢谢多多~~~

作者: biosxjj 发布时间: 2007-03-26

引用:

作者: biosxjj

哦我懂了 ...谢谢多多~~~

'多多'....
都是高中时太幼稚才起了这么一个奇怪的 ID, 现在想改 ID 又发现论坛似乎没有此功能; 想弃之又舍不得这 1000+ 回帖数....

作者: DoDo 发布时间: 2007-03-26

被你们忽悠了，想了好久，发现原来不过是：
int a,b
b = a % 16
a/13 = ((a/16)*16 + b) / 13 = (13*a/16)/13 + (3*a/16)/13 + b/13;
而己，然后再递归。

PS：多多其实是个蛮可爱的名字啊！^_^

作者: sighforever 发布时间: 2007-03-27

楼上的解释真精辟~~

作者: biosxjj 发布时间: 2007-03-27

按题意，加法也不能用吧？位运算记得只包括 ~ ^ & | << >> 六种。
想了个按位全加的函数，没严格测试过，这样楼主的答案比较完整了~

代码:

// 递归版
int bit_plus(int a, int b)
{
 int carry=(a&b)<<1;
 int sum=a^b;
 if(!carry)return sum;
 return bit_plus(carry,sum);
}

// 迭代版
int bit_plus2(int a, int b)
{
 int carry=(a&b)<<1;
 int sum=a^b;
 int temp_sum;
 while(carry)
 {
 temp_sum=carry^sum;
 carry=(carry&sum)<<1;
 sum=temp_sum;
 }
 return sum;
}

作者: soloforce 发布时间: 2007-03-27

现在完美了 ...可惜遭bs了当初我也忘记了全加器的写法~~~!!!~~~

作者: biosxjj 发布时间: 2007-03-27

引用:

作者: Lolita

按题意，加法也不能用吧？位运算记得只包括 ~ ^ & | << >> 六种。
想了个按位全加的函数，没严格测试过，这样楼主的答案比较完整了~

Lolita 兄好久不见，欢迎老大回来！

作者: DoDo 发布时间: 2007-03-27

DoDo 兄好！别叫我老大，多不好意思，要向你学习的东西多了呢！

作者: soloforce 发布时间: 2007-03-27

面试出这种题目没意思。所有成了气候的大公司的编码规范都不会允许用那种要让人看半天才懂的算法。学校里用用可以，真正工作时用反而会被BS的。

作者: masterdemon 发布时间: 2007-03-27