当前位置:C++技术网 > 资讯 > 深入讲解位与实现轮转遍历和特判的高效的运算代码技巧

深入讲解位与实现轮转遍历和特判的高效的运算代码技巧

更新时间:2015-06-27 01:07:55浏览次数:1+次

    本篇深入数字变化的本质规律,探讨了进制、掩码和轮转变化,应用到了巨量循环的轮转遍历和循环中的某个特别判断,极大提高程序性能。对于极致追求效率的程序来说,不可不掌握。
    虽然位运算大家都知道,但是能够应用于实际开发中的代码的人却不多。能够用到这些,一般也是基础很扎实的程序员了。
    下面来给大家分析一下位运算在代码中的应用的两个实用的例子。
    在《高!最全面经典的轮流策略实现技巧》中,已经讲过了位与运算在轮转中的应用,极大提高了运行效率。那么现在在进一步的分析,扩展应用,希望你掌握之后能够平时运用在实际的代码中。
    对于多元素的位与运算的轮转便利策略,只是提到了方法,虽然有些人能够明白。但是因为没有贴代码,可能有些人还是不明白。这里就进一步来分析一下。
    对于多个元素的实现代码如下:

int buf[3]={0};
for(int i=0;i<1000000000;i++)
{
    buf[i & 0x11]=0;
    //后面是其他操作
    ......
}

    这里只需要改变一个位与操作符后面的数字即可,是十六进制的表示0x开头还是十进制的(直接写数字),都可以。利用的原理就是i的递增,就可以数数一样,数字的累加,进制上的进位,会让对应的几个位,周期性的变化。对于一位来说,就是0和1之间的切换,而对于4位数之间的来说,就是0、1、2、3之间的切换,周而复始。而有几种数字就是几进制。这是进制的通用理解。所以,我们见到的各种进制,只是进制中的数字的种数不同罢了。究其本质,实际上都是多个数字的规律性的周而复始的变化而已。
     而不管是在哪种进制上,反应到计算机内部,都是二进制的形式表示。所以,我们任意取二进制的几个位,都可以发现他们是周而复始的循环的。比如一共有八个位,我们只观察其中任何一位,且数据一直在递增,每一个位都会呈现出一个周期性的反转。以最简单的最低一个,0,1,2,3,4,5... 在二进制里面,最低位为0,1,0,1,0,1...如此反复。只不过它的周期很短。如果用第两位来观察,那么便是0,0,1,1,0,0,1,1,...如此反复,周期变长,反转要的周期以所在的次幂来计算,也就是进制里面的权重。这个可以看进制的说明。第一位就是2的0次幂,第二位就是2的1次幂,如此类推。
    但是观察的几位,则是由一系列的数字轮流切换的,比如低两位,则是由0,1,2,3四位数来切换的。所以我们可以对两位进行0x11的位与,把其他的位屏蔽掉,只看低两位,这样就让他周而复始的变化,也就可以实现轮转。这样就可以对多个数组进行切换或者其他的应用。后面给出的0x11就是一个掩码,你要几位就用几个1。
    位与的其他一个应用,就是循环中的个别情况的判断,这个业内叫做特判,即特别判断。与之前的轮转不一样,这个只需要对一个数字进行识别,然后做出判断。所以,避免不了用判断。比如:
if(i%100==0)
{
    // - 第一百个特殊处理
}

    然而取模使用了除法运算再计算余数,效率没有位运算快。所以改进入下:
if(i&100==100)
{
    // - 第一百个特殊处理
}

    这里的应用,可以前面的轮转不太一样。更偏重的是掩码机制。你设置的数字,就是一个掩码,只有i与掩码100一样,才会完全的一对一的投过来,这样你得到的是100.这样就表明i为100。此时不是判断结果等于0哦,注意注意!掩码就如同一个模具,模具是什么样,最终完全与模具一样的东西才会被印出来,不一样的东西,就被阉割掉了。这也是掩码的原理。应用于此,就是循环中的特判。
    以上两个技巧那是使用的太普遍了,但是没有几个去深入研究。如此之后,在大循环中,不管是轮转还是特判,都可以用位与操作来实现,效率绝对比普通的提高了一个档次。这个不仅仅是用来装逼的,逼格绝对高,不是一般人看得懂的,且是实实在在是能够极大提高执行效率的。但是如果循环只有不超过百万级别,那也是大材小用了。如果是上亿,那不用位与,那就掉大了。