C语言中位运算的巧用

个人收集整理-ZQC语言中位运算的巧用语言中位运算的巧用发布于 周三 小左一 、位运算实例、用一个表达式，判断一个数是否是的次方（，.），不可用循环语句。：，转化成二进制是，。如果减则变成，。两者做按位与运算，结果如果为，则是的次方。、统计一个整数的二进制中的个数b5E2R。b5E2R。 ( ) ; (); ; ;二、位运算基础很多高级的动态规划题目或者一些基础的运算往往需要较高的执行效率和较低的空间需求，或者需要表示一些状态集合，而位运算刚好能满足这一切。很多的时候，恰当的位运算使用也能使程序变得更加简洁和优美。p1Ean。p1Ean。、位运算法则位运算是各位互不影响的，比如为而为，那么有 （的个数是取决于的类型的，这里认为的类型是位整型）另外两种位运算是位移运算。前者表示将的所有位向左移动位，后者则表示将的所有位向右移动位。对于非负整数（往往这也是我们最关心的），新空出的位将会被取代。比如为，而为，那么则为。大多数情况下可以简单地认为左移位就是乘以，而右移位则是除以（整除）。当然这是存在例外的对于负数是不能这么简单认为的：比如在 编译条件下，若，你会发现对于任何位移运算，无论的取值如何，其结果均为。因此请注意，在位移运算下务必确保对非负整数进行运算，以免发生不必要的问题。对于位移运算最常用的操作就是取一个特定的位比如就可以来表示一个状态集合集合中仅元素存在而没有任何其他元素因为其他的所有位均为。DXDiT。DXDiT。 、对于集合的表示大多数时候，我们可以用一个整数来表示一个包含不超过（当然如果使用位整型变量也可以是个）个元素的集合对于每一个位，如果元素为，则表示存在当前位所对应的集合成员，如果是，则表示这个集合成员是不存在的。比如 就可以表示集合，而上面提到的就表示集合。下面我们就能推导出一些直观的集合运算。我们定义 为全集即各二进制位均为的数。集合的并 集合的交 集合的差 补集 添加特定元素 清除特定元素 取出特定元素 判断是否存在特定元素 ()三、基本技术RTCrp。RTCrp。这里列举一些常用的位运算技术。、交换技术即不利用第三方进行数的交换，这里给出代码段。(, );、提取技术这里我们要做的就是找出变量最低位的和最高位的分别在什么位置。通过这些手段我们就能轻松地将一个集合分解为若干个元素。5PCzV。5PCzV。（） 低位技术低位技术即技术。相信熟悉树状数组（）的朋友应该并不陌生。我们对于一个非数，现在提取出其最低位的。这里我提三种不同的写法。()()()()()注意：这里我们求出的是中最后一个表示的数，而非其位置。可以发现，这三种低位函数的写法可谓大同小异均涉及到了和（其实 可以认为是和 () 等价的，这里利用了负数的存储原理）。的性质在于：其将一个数最后一个变成了，并把原来这个之后的位置均变成了。低位技术正是利用了这个性质。举一个简单的应用的例子 ) ( );()表示是的多少次方 (, ( ); ;上述程序的复杂度为严格的(!)，而非()。这里只是一个说明，并没有特指全排列问题这种方式在很多地方可以大大提高程序效率。xHAQX。xHAQX。（）特殊情况下的简单想法对于低位技术，一个最简单的想法就是按位扫描依次判断当前位是否为，这个算法似乎是很慢的对于一个位的二进制数，最坏情况需要扫描次！但是这只是最坏而非一般当情况特殊一些我们要求的不是的最低位，而是要求出这所有数的低位！那么在这种情况下，看似缓慢的暴力算法其实是非常不错的这种算法大约只要均摊次扫描即可完成检索。这实际上是最快的方式了。LDAYt。LDAYt。（）利用分块思想我们可以打一张的表，用于记录每个数的低位（或者是高位），那么对于位的整数，就可以将其分解为个位整数利用预处理得到的表迅速求出低位或者高位了。Zzz6Z。Zzz6Z。（）利用编译器的内置函数这是语言的又一大优势。这里略微提一下两个位处理指令：（前向位扫描）和（反向位扫描）。这两种指令都是内置且非常高效率的。而令人高兴的是编译器就存在这两种基于这种原理的位处理函数：（统计最高位的个数）和（统计低位的个数）。这是对于和编程者最方便和快捷的位处理方式了。不过要注意的是这两个函数对于都没有定义，因此需要特别小心！dvzfv。dvzfv。、计算二进制表示中的个数我们很容易判断一个数是不是的整次幂比如对于，那么只要判断()是否为就可以了。不过很多时候我们需要统计二进制位中有多少个（比如当表示一个集合的时候，我们想知道这个集合中元素的个数），这就要麻烦一点了。（）暴力方式我们可以不断地使用低位技术消去最后一个。不过这个方法很慢。rqyn1。rqyn1。（）预处理我们可以利用递推形式计算出我们所需要的答案，方式非常简单。用 来记录的二进制表示中的个数，那么： ( )这样就能在线性时间下计算出结果了。Emxvx。Emxvx。（）利用内置函数有一个函数 就是实现了我们需要的功能不过比较遗憾的是，这个函数的实现并不像那样利用硬件指令，相反的，它用了一个类似基于预处理方式的按位扫描的实现方式不过它仍然很高效。SixE2。SixE2。（）有趣的代码这里再给出一段可以实现上述功能的代码，有兴趣的读者可以自行研究。() 为位符号非负整数，或者位无符号类型 (); ()(); (); (); (); ; 、枚举子集当一个数的二进制表示一个集合的时候，位运算的一个巨大优点在于其可以非常轻松和高效地枚举当前集合的所有子集。它的性质在于如果是的真子集，那么可以保证枚举子集的次数一定小于枚举的子集的次数。这一点可以大大提高很多压位动态规划题目的实现效率。6ewMy。6ewMy。（）暴力的方式最暴力的方式莫过于枚举所有可能的集合，然后一一判断是否为当前集合的子集。如果需要枚举的集合是个元素的集合，那么对所有可能集合都进行一次枚举操作，花费的时间为()()。kavU4。kavU4。（）高效的方式假设全集有个元素,那么所有可能的集合就有个,对于任意子集,用位进制简单枚举的所有子集,个数就有个,因此如果对所有集合都进行这样一次枚举操作,那么总的时间复杂度就是()()。高效的方式。这里的技巧和低位技术的技巧是类似的当我们取出最后一个的时候，这个将变成，而比其低位的将变成。与低位技术不同的是，我们并不是要提出某一位，而是要去除某一位的，并补上一些我们需要的。所以假设当前集合为，那么枚举的代码段则为y6v3A。y6v3A。() ; ( ) ( ) ;若当前为位二进制的集合，并且对所有可行集合进行上述操作，可以证明，操作的总次数为()。四、有趣的技巧、计算绝对值( ) ; ()也可写作 () 这里需要注意的是，上面的, 默认为位有符号整数。、按位翻转()()()()()();M2ub6。M2ub6。如果无符号位整数()，那么经过上述操作后()。、枚举恰好含有个元素的集合我们假设全集为含有个元素为 ,，那么代码段可以写成： ( ) ; (!( ( ) 来避免除法运算。：, 算法, 优化,一 、位运算实例、用一个表达式，判断一个数是否是的次方（，.），不可用循环语句。：，转化成二进制是，。如果减则变成，。两者做按位与运算，结果如果为，则是的次方。、统计一个整数的二进制中的个数 ( ) ;0YujC。0YujC。 (); ; ;二、位运算基础很多高级的动态规划题目或者一些基础的运算往往需要较高的执行效率和较低的空间需求，或者需要表示一些状态集合，而位运算刚好能满足这一切。很多的时候，恰当的位运算使用也能使程序变得更加简洁和优美。eUts8。eUts8。、位运算法则位运算是各位互不影响的，比如为而为，那么有 （的个数是取决于的类型的，这里认为的类型是位整型）另外两种位运算是位移运算。前者表示将的所有位向左移动位，后者则表示将的所有位向右移动位。对于非负整数（往往这也是我们最关心的），新空出的位将会被取代。比如为，而为，那么则为。大多数情况下可以简单地认为左移位就是乘以，而右移位则是除以（整除）。当然这是存在例外的对于负数是不能这么简单认为的：比如在 编译条件下，若，你会发现对于任何位移运算，无论的取值如何，其结果均为。因此请注意，在位移运算下务必确保对非负整数进行运算，以免发生不必要的问题。对于位移运算最常用的操作就是取一个特定的位比如就可以来表示一个状态集合集合中仅元素存在而没有任何其他元素因为其他的所有位均为。sQsAE。sQsAE。 、对于集合的表示大多数时候，我们可以用一个整数来表示一个包含不超过（当然如果使用位整型变量也可以是个）个元素的集合对于每一个位，如果元素为，则表示存在当前位所对应的集合成员，如果是，则表示这个集合成员是不存在的。比如 就可以表示集合，而上面提到的就表示集合。下面我们就能推导出一些直观的集合运算。我们定义 为全集即各二进制位均为的数。集合的并 集合的交 集合的差 补集 添加特定元素 清除特定元素 取出特定元素 判断是否存在特定元素 ()三、基本技术GMsIa。GMsIa。这里列举一些常用的位运算技术。、交换技术即不利用第三方进行数的交换，这里给出代码段。(, );、提取技术这里我们要做的就是找出变量最低位的和最高位的分别在什么位置。通过这些手段我们就能轻松地将一个集合分解为若干个元素。TIrRG。TIrRG。（）低位技术低位技术即技术。相信熟悉树状数组（）的朋友应该并不陌生。我们对于一个非数，现在提取出其最低位的。这里我提三种不同的写法。()()()()()注意：这里我们求出的是中最后一个表示的数，而非其位置。可以发现，这三种低位函数的写法可谓大同小异均涉及到了和（其实 可以认为是和 () 等价的，这里利用了负数的存储原理）。的性质在于：其将一个数最后一个变成了，并把原来这个之后的位置均变成了。低位技术正是利用了这个性质。举一个简单的应用的例子 ) ( );()表示是的多少次方 (, ( ); ;上述程序的复杂度为严格的(!)，而非()。这里只是一个说明，并没有特指全排列问题这种方式在很多地方可以大大提高程序效率。lzq7I。lzq7I。（）特殊情况下的简单想法对于低位技术，一个最简单的想法就是按位扫描依次判断当前位是否为，这个算法似乎是很慢的对于一个位的二进制数，最坏情况需要扫描次！但是这只是最坏而非一般当情况特殊一些我们要求的不是的最低位，而是要求出这所有数的低位！那么在这种情况下，看似缓慢的暴力算法其实是非常不错的这种算法大约只要均摊次扫描即可完成检索。这实际上是最快的方式了。zvpge。zvpge。（）利用分块思想我们可以打一张的表，用于记录每个数的低位（或者是高位），那么对于位的整数，就可以将其分解为个位整数利用预处理得到的表迅速求出低位或者高位了。NrpoJ。NrpoJ。（）利用编译器的内置函数这是语言的又一大优势。这里略微提一下两个位处理指令：（前向位扫描）和（反向位扫描）。这两种指令都是内置且非常高效率的。而令人高兴的是编译器就存在这两种基于这种原理的位处理函数：（统计最高位的个数）和（统计低位的个数）。这是对于和编程者最方便和快捷的位处理方式了。不过要注意的是这两个函数对于都没有定义，因此需要特别小心！1nowf。1nowf。、计算二进制表示中的个数我们很容易判断一个数是不是的整次幂比如对于，那么只要判断()是否为就可以了。不过很多时候我们需要统计二进制位中有多少个（比如当表示一个集合的时候，我们想知道这个集合中元素的个数），这就要麻烦一点了。（）暴力方式我们可以不断地使用低位技术消去最后一个。不过这个方法很慢。fjnFL。fjnFL。（）预处理我们可以利用递推形式计算出我们所需要的答案，方式非常简单。用 来记录的二进制表示中的个数，那么： ( )这样就能在线性时间下计算出结果了。tfnNh。tfnNh。（）利用内置函数有一个函数 就是实现了我们需要的功能不过比较遗憾的是，这个函数的实现并不像那样利用硬件指令，相反的，它用了一个类似基于预处理方式的按位扫描的实现方式不过它仍然很高效。HbmVN。HbmVN。（）有趣的代码这里再给出一段可以实现上述功能的代码，有兴趣的读者可以自行研究。()为位有符号非负整数，或者位无符号类型) (); ()(); (); (); (); ; V7l4j。V7l4j。、枚举子集当一个数的二进制表示一个集合的时候，位运算的一个巨大优点在于其可以非常轻松和高效地枚举当前集合的所有子集。它的性质在于如果是的真子集，那么可以保证枚举子集的次数一定小于枚举的子集的次数。这一点可以大大提高很多压位动态规划题目的实现效率。83lcP。83lcP。（）暴力的方式最暴力的方式莫过于枚举所有可能的集合，然后一一判断是否为当前集合的子集。如果需要枚举的集合是个元素的集合，那么对所有可能集合都进行一次枚举操作，花费的时间为()()。mZkkl。mZkkl。（）高效的方式假设全集有个元素,那么所有可能的集合就有个,对于任意子集,用位进制简单枚举的所有子集,个数就有个,因此如果对所有集合都进行这样一次枚举操作,那么总的时间复杂度就是()()。高效的方式。这里的技巧和低位技术的技巧是类似的当我们取出最后一个的时候，这个将变成，而比其低位的将变成。与低位技术不同的是，我们并不是要提出某一位，而是要去除某一位的，并补上一些我们需要的。所以假设当前集合为