在编写程序解决某些问题时，可以灵活地使用进位制数，例如像二进制枚举就是灵活使用二进制数。下面再讲述一些例题。
1、二进制的应用
【例1】至少一位数字相同
问题描述
给定N个正整数A1，A2，...，AN，求有多少整数对(i,j)，满足以下条件：
1≤i<j≤N，Ai和Aj至少有一位数字是相同的（不一定要在相同的数位）。
输入
输入的第一行包含一个正整数N。
接下来N行，每行包含一个正整数Ai。
输出
输出一行一个整数，表示满足条件的整数对的数目。
输入样例
4
32
51
123
282
输出样例
4
（1）编程思路。
以样例为例说明。共有4组整数对满足条件。（32，123）、（32，282）、（51，123）和（123，282）。
显然，若采用二重循环两两组合来判断每组数中是否至少有一位数字是相同的，在数据量较大的情况下，不是一个可取的方法。
实际上要判断两个整数是否至少有一位数字是相同的。我们是不在乎两个数的每一个数位是什么、哪几个位上的数字相同，只用关心0~9这9个数字中是否有某个数字在两个数中都出现过，若都出现过，则两个数至少有一位数字是相同的。
由于十进制中只有0~9共10个数码，因此可以用一个10位的二进制数来表示一个十进制整数X的类型，这个二进制数的第k（0≤k≤9）位为1表示整数X中含有数字k，若数字k在整数X中没出现，则对应二进制数的第k位为0。
用数组a来保存各类型整数的个数，显然任何一个正整数的类型一定在 [0,1023]之间。即数组a最多有1024个元素。初始时，数组a的元素值全部置为0。
还是以样例中的4个数为例。
整数32中含有2、3这两个数字，对应二进制数为0000001100，数的类型号为12，a[12]加1，a[12]=1。
整数51中含有1、5这两个数字，对应二进制数为0000100010，数的类型号为34，a[34]加1，a[34]=1。
整数123中含有1、2、3这3个数字，对应二进制数为0000001110，数的类型号为14，a[14]加1，a[14]=1。
整数282中含有2、8这两个数字，对应二进制数为0100000100，数的类型号为260，a[260]加1，a[260]=1。
这样处理后，再求N个正整数中满足要求的整数对的数量ans（初值为0）就很方便了。分两种情况处理。
1）两个整数的类型相同，则同类型中任意取两个数就满足要求。用循环对a[0]~a[1023]中各a[i]值进行遍历。若 a[i]!=0，则 ans=ans+a[i]*(a[i]-1)/2。
2）两个整数的类型不同。设一个类型为i，一个类型为j （设i<j），若 i & j的值不为0，则i和j对应的二进制数一定在某个位上都是1，也就是存在相同的数字（某个位都为1）。这样，a[i]和a[j]中各取1个数就满足要求。 ans=ans+a[i]*a[j]。
（2）源程序。
#include <stdio.h> int main() { int n; scanf("%d",&n); int i,j; long long a[1024]={0}; int min=1024,max=0; for (i=1;i<=n;i++) { long long x; scanf("%lld",&x); int h[10]; // 记录0~9每个数字在x中是否出现 for (j=0;j<10;j++) h[j]=0; while(x) { h[x%10]=1; // 数字x%10出现了，h[x%10]记为1 x/=10; } int num=0; for (j=0;j<10;j++) { num=num*2+h[j]; // 将h[0]~h[9]中保存数据作为二进制数转换为十进制数num } a[num]++; // num这种数增加1个 if (num>max) max=num; if (num<min) min=num; } long long ans=0; for (i=min;i<=max;i++) // 同一种数内两两组合 ans+=a[i]*(a[i]-1)/2; for (i=min;i<max;i++) // 不同种类的数两两组合 { for (j=i+1;j<=max;j++) if (i & j) ans+=a[i]*a[j]; } printf("%lld\n",ans); return 0; }
将上面的源程序提交给洛谷题库 P7617 [COCI2011-2012#2] KOMPI?I （https://www.luogu.com.cn/problem/P7617），可以Accepted。
【例2】异或和
问题描述
给定一个长度为N的序列A1，A2，...，AN，求序列元素两两异或的总和。
例如，某序列中有3个数，A1=7，A2=3，A3=5。
则有 A1 ? A2 = 4，A1 ? A3 = 2，A2 ? A3 = 6，
4 + 2 + 6 = 12，因此序列元素两两异或的总和为12。
输入
输入的第一行包含一个正整数N（1≤N≤106）。
接下来N行每行包含一个正整数Ai（1≤Ai≤106）。
输出
输出一行一个整数，表示两两异或后的总和。
输入样例
3
7
3
5
输出样例
12
（1）编程思路。
若通过二重循环对序列中的数据进行两两组合求异或和，在数据量大的情况下肯定是超时的。
首先，我们考虑一个数转成二进制后每个位的操作，每个位上的数据只能是0或1，其异或运算规则是： 0和1 异或得1 ， 1和1 或者 0和 0 异或得0 。怎么求多个0 和1 的两两异或和呢？
举个例子： 0，1，0 三个数两两异或和应该是：0 异或 1 加上 0 异或0 再加上 1 异或 0，和值sum=1+0+1=2 。从中可以发现，每个 0 和一个 1 进行异或，和sum 就要加 1 ，也就是说每一个 0 都会使 sum 加上 1 的个数（因为 0 要和 1 的个数个 1 异或）。设在n