#11091. 汉明距离总和

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。

给你一个整数数组 a,请你计算并返回 a 中任意两个数之间 汉明距离的总和 。

输入格式

第一行:n

第二行:n个整数

输出格式

汉明距离总和

样例

输入1:

3
4 14 2

输出1:

6

解释:在二进制表示中,4 表示为 0100 ,14 表示为 1110 ,2表示为 0010 。(这样表示是为了体现后四位之间关系)

所以答案为:汉明距离(4, 14) + 汉明距离(4, 2) + 汉明距离(14, 2) = 2 + 2 + 2 = 6

输入2:

3
4 14 4

输出2:

4

数据范围与提示

1 <= n <= 10^4

0 <= a[i] <= 10^9

给定输入的对应答案符合 32-bit 整数范围