掩码+异或的作用

• 前言
• 一、按位与为零的三元组
• 二、统计分组
• • 1、map统计分组
  • 2、异或+掩码
• 总结
• 参考资料

前言

当a + b = 0时，我们能够很清楚的知道b是个什么值，b = 0 - a = -a，如果当a & b = 0时，我们能够很清楚的知道b是什么值吗？

一、按位与为零的三元组

二、统计分组

1、map统计分组

像这种组合题，纯靠for循环遍历出来的都会超时，一般用map/切片统计，通过乘法/加法，快速组合，或者说抽象的方式组合，只在乎组合的次数，不在乎具体的组合情况。
方法：先两层for循环，进行统计两数与完之后的分组情况，再来两层for循环，来寻找分组数据和第3个数与的情况。

func countTriplets(nums []int) int {// 分组cnt := map[int]int{}for i := 0;i < len(nums);i++ {for j := 0;j < len(nums);j++ {cnt[nums[i] & nums[j]]++}}// 计数ans := 0for k,v := range cnt {if k == 0 {ans += v * len(nums)continue}for _,n := range nums {if n & k == 0 {ans += v}}}return ans
}

2、异或+掩码

上面的解法只是进行了简单的分组，但是并未利用到与操作的特性，我们可以仔细分析与操作的特性，看能不能将第二个双层for循环变成单层for循环。

与操作为0，说明了三个数的每一位，必定有一个0及以上。
假设第一个双层for循环得到了一些数，这些数要和nums再组合一次，当前者的任意一位为1时，后者必须是0，当前者的任意一位为0时，后者可0可1。

可0可1？那怎么记录前者的“相反数”啊？
将一个值整成多份，每份将一个0变1，并记录这种数有一个，这样就不管匹配的什么可0可1了。
我们需要记录所谓的相反数，可通过掩码+异或的方式，来将0变1，1变0，再不断组合1的情况，并记录这些相反数的个数。

func countTriplets(nums []int) int {// 分组统计cnt := make([]int,1 << 16)cnt[0] = len(nums)const MAX = 1 << 16 - 1for i := 0;i < len(nums);i++ {mask := nums[i] ^ MAXfor j := mask;j > 0;j = (j - 1) & mask {cnt[j]++}}// 计数ans := 0for _,a := range nums {for _,b := range nums {ans += cnt[a & b] // 刚好01互补，mask+异或是个好东西}}return ans
}

总结

1）困难题都是各种组件组合而成，所以训练好各种问题的解决方式，再分析困难题的组合情况，就能快速解答困难题。
2）异或的作用蛮大的，配合掩码能将一个数的所有二进制取反。

参考资料

[1] LeetCode 按位与为零的三元组