Chinaunix

标题: 求助，这个代码是什么意思？ [打印本页]

作者: yangfan876 时间: 2013-05-03 22:15
标题: 求助，这个代码是什么意思？
大家好，这里是维基百科上面归并排序递归的代码，

void merge_sort(int array[], unsigned int first, unsigned int last)
{
int mid = 0;
if(first<last)
{
/*mid = (first+last)/2;*/ /*注意防止溢出*/
/*mid = first/2 + last/2;*/
/*mid = （(first & last) + (first ^ last) >> 1);*/
mid = ((first & last) + ((first ^ last) >> 1)); /*修正上一句优先级错误*/
merge_sort(array, first, mid);
merge_sort(array, mid+1,last);
merge(array,first,mid,last);
}
}

复制代码

大家看看前面注释掉的代码，第一句是会产生溢出，可以理解，但是第二句应该是可以解决溢出的问题的，那么位运算的那句（未被注释的），要怎么理解？我对位运算很不感冒，求大神指教....

作者: 群雄逐鹿中原 时间: 2013-05-03 22:19
本帖最后由群雄逐鹿中原于 2013-05-03 22:30 编辑

看不懂啊

作者: linux_c_py_php 时间: 2013-05-03 22:30
归并排序用递归已是屌丝至极..

作者: hbmhalley 时间: 2013-05-03 22:38
我有一梨一杏一桃, 你有一杏一桃一桃核, 咱俩好基友对半分, 混一块又切不动
于是各留一杏一桃, 单切梨和桃核

作者: __BlueGuy__ 时间: 2013-05-03 22:49

linux_c_py_php 发表于 2013-05-03 22:30
归并排序用递归已是屌丝至极..

你脑子有问题吗？不递归你怎么写？

作者: linux_c_py_php 时间: 2013-05-03 22:50
本帖最后由 linux_c_py_php 于 2013-05-04 00:58 编辑

__BlueGuy__ 发表于 2013-05-03 22:49
你脑子有问题吗？不递归你怎么写？

... xxxxxxxxx

作者: __BlueGuy__ 时间: 2013-05-03 22:53
本帖最后由 __BlueGuy__ 于 2013-05-03 23:10 编辑

linux_c_py_php 发表于 2013-05-03 22:50
... 你妈死了, 归并排序还用得着递归, 就你还能写游戏, 呵呵.

你妈到死了，你全家都死了

你感觉游戏很难是吗？

我不仅不会，而且我还懒的会，你感觉会非递归归并排序很牛B吗？
我发现你很有意思，不会归并排序就不能写游戏了？

游戏就一定会用到排序？一定会用到归并排序？
会冒泡排序不行？会 qsort、会 STL 的sort 不行？

不会归并排序就不能写游戏？是你妈教你的逻辑吗？
你跟网易吴云洋是一个思维，非要会这个会那个然后才能做游戏

回炉再造吧！

作者: linux_c_py_php 时间: 2013-05-03 23:12
本帖最后由 linux_c_py_php 于 2013-05-03 23:12 编辑

__BlueGuy__ 发表于 2013-05-03 22:53
你妈到死了，你全家都死了

你感觉游戏很难是吗？

咩哈哈, 不会就不会吧, 何必费那么多口舌, 去搞会不就行了?

作者: __BlueGuy__ 时间: 2013-05-03 23:13

linux_c_py_php 发表于 2013-05-03 23:12
咩哈哈, 不会就不会吧, 何必费那么多口舌, 去搞会不就行了?

没时间
搞你妹到有时间！

作者: __BlueGuy__ 时间: 2013-05-03 23:18
百度一搜一大堆，还用的着我去搞会吗？
顺便问一下，你有妹妹吗

作者: __BlueGuy__ 时间: 2013-05-03 23:31
/*mid = (first+last)/2;*/ /*注意防止溢出*/
/*mid = first/2 + last/2;*/
/*mid = （(first & last) + (first ^ last) >> 1);*/
mid = ((first & last) + ((first ^ last) >> 1)); /*修正上一句优先级错误*/

我是第一次见到有人写程序仿止溢出

作者: yangfan876 时间: 2013-05-03 23:38
呃～这个问题焦点只是那几句判断mid的值的问题，大家～～呃～呵呵～没有必要为这个伤和气～呵呵

作者: Frahm 时间: 2013-05-04 13:46
本帖最后由 Frahm 于 2013-05-04 13:52 编辑

first + last => (first & last)<<1 + ((first ^ last))
(first + last)>>1 => (first & last) + ((first ^ last)>>1)

first&last是得到进位的位，first ^ last是不考虑进位的相加值，剩下的就很明显了

作者: zheguzai 时间: 2013-11-18 17:12

作者: kdkgod 时间: 2013-11-19 21:57
有意思吗，动不动就骂人。

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)