29 条评论

  • chnlkw

    swap(a,b)
    {
    a:=a xor b
    b:=a xor b
    a:=a xor b
    }

    回复:好东西,谢谢分享

  • chnlkw

    n皇后能解释具体点吗?

    回复:row、ld和rd分别表示这一行考虑纵列和两个对角线限制后的状态,“1”表示该位置不能放皇后。row or ld or rd的操作把所有的“1”都合在了一起,取反后再取末n位后的“1”就是这一行还可以放皇后的位置(即pos)。后面的p不断地提取pos中的“1”并进行递归。自己单步一下吧,虽然单步很麻烦(因为还要转二进制)。

  • windywinter

    Matrix67牛能不能把在交在USACO的代码全贴出来?我想知道这样做怎么纪录每个皇后的位置。总不能用log2(p)来求皇后所在的列吧?

    回复:USACO的那道题只需要输出字典序最前面的三种方案的位置和所有方案总数,而前者可以用普通的深搜完成(只搜3个不拖时间)。USACO那道题的代码在我发布的NOIp集训资料里有。

  • 逆铭

    手工单步了一遍四皇后,终于明白拉~

  • 狗狗

    swap还有很多种写法..记得baidu Pascal吧里面有一个帖子..

    回复:我记得一个
    a:=a+b;
    b:=a-b;
    a:=a-b;

  • YETIboy

    关于位运算的交换和通过一个中间变量来交换,虽然位运算有着吸引“眼球”的外衣,但她比起后者需要更多的时间,也就是编译后需要更多的汇编指令。。。我查看C语言程序反汇编生成的汇编代码(linux下的AT&T汇编),或是用gprof工具分析了各自运行100000000次的时间。。。得出老上面的结论:)

    回复:谢谢你提供的资料

  • Planeyang

    美好的东西啊,多美的皇后问题啊。
    推荐这本书(《高效程序的奥秘》),里面讲了N多的位运算来优化。

    回复:下载到这本书了(英文原版chm),太牛了,看来这篇日志又要加内容了

  • 逆铭

    20号又更新拉~~看来需要持续关注此帖呢~

    回复:根据Planeyang的评论,这个月我还要更新;我想把这篇日志置顶了

  • 逆铭

    关注并期待中…

  • yiyi

    Matrix67牛的文章实在太好了.
    看了收益匪浅!

    你可以把那本Hacker's Delight,
    发到我的邮箱吗?
    (我没找到)
    yiyiyoung@gmail.com

    严重感谢!!!

  • yiyi

    刚刚找到

    不用麻烦大牛了

    也谢谢

  • richardxx

    这篇文章确实好,希望看到更多好文章。。

  • yiyi

    Matrix67牛,
    上面习题的倒数第2题,
    答案可能有误:
    "取右边连续的1(100101111->1111)  x xor (x+1) shr 1"
    shr的优先级大于xor,
    似乎改为(x xor (x+1)) shr 1更妥.

    回复:哦对,谢谢提醒。已更正

  • xLight

    为什么我用gcc4.1 编译的 异或运算 比 临时变量 的指令少啊

  • mikew

    这样见得快一些吗?

  • mikew

    顶层,这样见得快一些吗?

  • AbnerZheng

    链接坏了,matrix能否更新下?

回复给 狗狗 取消回复

  +  84  =  91