位运算 - 异或求和

2024-09-05 17:08

文章标签 运算求和异或

本文主要是介绍位运算 - 异或求和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

异或求和

Problem's Link: http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1254

Mean:

Description
给你2个区间[A,B]和[C,D],现在只要求你求出区间[A,B]和[C,D]内任意2个整数异或后的和，因为答案可能会很大，你只需将结果%mod即可。
For(i:A→B)
For(j:C→D)
Sum += (i^j);
Input
输入第一行为T(T<=15),表示测试的数据组数，第2行到T+1行，每行5个数字，分别为A,B,C,D,mod.
(1<=A,B,C,D<2^31,A<=B,C<=D,1<=mod& lt;=1,000,000,007),即为上述的数值。
Output
输出有T行，每行有一个数字，代表题述的答案（即Sum % mod）。
Sample Input
3
5 11 9 12 43
9 12 5 11 83
1 1 2 2 3
Sample Output
18
24
0

analyse:

看到这么大的输入，再看看时限是500ms，开始有点摸不着头脑，看来只能用log(n)的方法来做了。

典型的位运算题目。

首先我们求出[A,B]区间中所有数各个位上1的个数。比如[1~8]就是1,4,4,4；

怎么求呢？

我们可以打表找一下规律：

1: 0001

2: 0010

3: 0011

4: 0100

5: 0101

6: 0110

7: 0111

8: 1000

9: 1001

.....

我们会发现，[1,n]中第k位总共1的个数就是：n/(k<<1) *(k<<1 /2 )。或者说：符合 x mod 2^k >=2^（k-1）的 x 第k位就是1。

额，这个要自己去找规律。

要求[A~B]区间内各位上1的个数，只需要B1[i]-A1[i]就行。

同理，我们可以求出[C~D]区间上各位1的个数。

剩下的就是怎么求和了。

求和比较简单：

区间【A,B】第k位为1的个数乘以区间【C,D】第k位为0的个数+区间【A,B】第k位为0的个数乘以区间【C,D】第k位为1的个数）*2^(k-1)。

Time complexity: O(logn)

Source code:

 /* 
 * this code is made by crazyacking 
 * Verdict: Accepted 
 * Submission Date: 2015-08-05-11.38 
 * Time: 0MS 
 * Memory: 137KB 
 */ 
 #include <queue> 
 #include <cstdio> 
 #include <set> 
 #include <string> 
 #include <stack> 
 #include <cmath> 
 #include <climits> 
 #include <map> 
 #include <cstdlib> 
 #include <iostream> 
 #include <vector> 
 #include <algorithm> 
 #include <cstring> 
 #define  LL long long 
 #define  ULL unsigned long long 
 using namespace std; 
 
 void get1( LL n , LL arr []) { /**< 求1~n所有数各个位上1的个数之和 */ 
       for( int i = 1; i < 32; ++ i) arr [ i ] = 0; 
       for( LL i = 1 , f = 2 ,b = 1; b <=n; ++ i , f <<= 1 ,b <<= 1) { 
             arr [ i ] =(n / f) *( f / 2); /**< 对于每一位,1~n可分为n/t组(t是每组的01数量)，其中每组有t/2个是1 */ 
             if(n % f >=b) arr [ i ] +=(n % f -b + 1); /**< 加上余数部分 */ 
       } 
 } 
 
 int main() { 
       ios_base :: sync_with_stdio( false); 
       cin . tie( 0); 
       LL n , t; 
       cin >> t; 
       while( t --) { 
             LL A ,B , C , D , Mod , a1 [ 32 ], b1 [ 32 ], c1 [ 32 ], d1 [ 32 ]; 
             cin >> A >>B >> C >> D >> Mod; 
             get1( A - 1 , a1); get1(B , b1); get1( C - 1 , c1); get1( D , d1); 
             LL ab1 [ 32 ], ab0 [ 32 ], cd1 [ 32 ], cd0 [ 32 ]; 
             for( int i = 1; i < 32; ++ i) ab1 [ i ] = b1 [ i ] - a1 [ i ], cd1 [ i ] = d1 [ i ] - c1 [ i ]; 
             int l1 =B - A + 1 , l2 = D - C + 1; 
             for( int i = 1; i < 32; ++ i) ab0 [ i ] = l1 - ab1 [ i ], cd0 [ i ] = l2 - cd1 [ i ]; 
             LL sum = 0 , base = 1; 
             for( int i = 1; i < 32; ++ i) 
                   sum =( sum +( base <<( i - 1)) % Mod *( ab0 [ i ] % Mod * cd1 [ i ] % Mod + ab1 [ i ] % Mod * cd0 [ i ] % Mod) % Mod) % Mod; 
             cout << sum << endl; 
       } 
       return 0; 
 } 
 /* 
 
 */ 