【在线编程产品介绍】
阿里云开发者社区在线编程：
免费刷题大神器，助你拿到好offer
周赛月赛不停歇，做题还能领奖品
大赛笔试全真题，常做常新有惊喜
点击链接开始产品体验：https://developer.aliyun.com/coding
本文为大家介绍的是“40题.2的幂次方数”的解法探究。先来看一下题目内容：
题目详情
等级：中等
知识点：数学、枚举
查看题目：2的幂次方数
Tom是一个十分喜欢数学的人，尤其喜欢2的幂次方的数字。现有 n（1<=n<=150000）个数字，对于其中的每一个数字 ai(1<=i<n, 1<=ai<=1000000000)，Tom希望找到除了它自己以外的一个数 aj( i != j )，使得 ai+aj 是一个2的幂次方数，如果找不到就将这个数删除，问最终需要删除多少个数字?
输入数字个数n和n个数字；
输出一个数字，表示最终需要删除的数字的个数。
示例1
输入：
3
[1,2,3]
输出：
1
解题方法 ：位运算
对于本题，因为要从数组中删除数字。删除分为两步，一是定位（查找），二是删除（将出现次数减1）。所以首先需要考虑的难题是，如何快速定位要查找的数字，并记录下数字出现的次数？for循环的线性查找，递归的二分查找（对有序数组），建立哈希表，都是可选的方式。既然追求最佳解法，你不妨先试试将题目提供的数据结构转为哈希表？
之后的第二个难点，就是如何得出“与某个数相加为2的幂次方数”的数字了。我们知道，用二进制表示时，一个2的幂次方的正整数，譬如2，4，8，16...，只有最高位为1，其余位都是0，譬如b1，b10，b100，b1000...所以，对每个数字，只要用位元算找到它的最高位1的位置，就可以确定比它大的2的幂次方数中最小的数字了。
本题最后的陷阱，在于正确理解 “与这个数相加为2的幂次方数”的条件。举个例子来说，对于数字1，它不仅与1相加为2的幂次方数，与3，7，15...相加后，结果都是2的幂次方数。很多同学想到位运算的时候，可能忽略了这个条件，而只考虑了比数字大的2的幂次方数中最小的数字
时间复杂度：O(31n)（考虑到本题Integer正整数所占的二进制位数
空间复杂度：O(n)
看完之后是不是有了答题思路了呢，快来练练手吧：第40题.2的幂次方数