2的幂2 n次不正确 - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

算法训练 2的次幂表示

问题描述　　任何一个正整数都可以用2进制表示，例如：137的2进制表示为10001001。　　...将这种2进制表示写成2的次幂的和的形式，令次幂高的排在前面，可得到如下表达式：137=2^7+2^3+2^0 　　现在约定幂次用括号来表示，即a^b表示为a（b）　　此时，137可表示为：2（...输入格式　　正整数（1n<=20000）输出格式　　符合约定的n的0，2表示（在表示中不能有空格）样例输入 137 样例输出 2(2(2)+2+2(0))+2(...]; while(N > 0){ int tmp = N % 2; if ( tmp == 1){ num...[j++] = i; } i++; N = N / 2; } j--; for (

6152 0

例3 检测2的幂次

class Solution: def checkPowerOf2(self, n): ans=1 for i in range(31):...if ans == n: return True ans = ans << 1 return False if __name__...=="__main__": temp = Solution() nums1 = 16 nums2 = 17 print(("输入: " + str(nums1)))...print(("输出: " + str(temp.checkPowerOf2(nums1)))) print(("输入: " + str(nums2))) print(("输出: " +...str(temp.checkPowerOf2(nums2)))) 结果如下: 输入: 16 输出: True 输入: 17 输出: False

4763 0

您找到你想要的搜索结果了吗？

是的

没有找到

一文看懂HashMap扩容为什么是2的n次幂

如果存放相同的Key，那么Value将会被覆盖，类似于QQ更改密码，账号不会变，只有密码会进行更改。 ? 运行结果如下所示 ? 2.为什么扩容2的n次幂？...首先先看一下HashMap中的putVal方法(存值的)和resize方法(扩容的)，之所以HashMap扩容是2的n次幂和这两个方法有千丝万缕的联系。...通过putVal方法可以看出来HashMap在存值时会先把key的hash值和扩容后的长度进行一次按位与运算，其中hash是在hash方法中把key进行计算后的出来的结果，n是扩容的长度（也就是数组的长度...之所以这样2n扩容和上面的两个方法有极大的关系，首先他们都使用了按位与运算，按位与运算就是把值先变成二进制然后进行运算，如果有0则为0，都为1时则输出为1，HashMap默认容量为16那么在存放到数组时就是...通过上面的对比可以看出来11111111和其他值比较大大的减少了hash碰撞的发生，这样就是为什么HashMap为什么扩容采用2的n次幂的原因。

6.6K9 0

O(1)时间检测2的幂次除以2统计1的位数n和n-1取且

用 O(1) 时间检测整数 n 是否是 2 的幂次。样例 n=4，返回 true; n=5，返回 false. 除以2 这个当然是很简单也最容易想到，int的话可能要除31次才能出来。...统计1的位数这个也容易想到，如果是2的幂次的话肯定是正的，然后去统计1的个数，需要移位和取且操作，和上面的方法差不多。因为除2本来就可以通过移位操作完成。...bool checkPowerOf2(int n) { if(n<=0) return false; return !...n位有符号数的表示范围： -2^n-- 2^(n-1)-1 原码的表示：　　　　左边是符号位，正数为0，负数为1。...CPU的加法器简单效率高，因此不需要再专门实现减法器。在8位字中，我们的模就是2的8次方，即256。

7723 0

2的幂

题目描述难度级别：简单给定一个整数，编写一个函数来判断它是否是 2 的幂次方。...n大于1时，对其进行迭代，通过对连续2取模判断是否等于0，当遇到不为0时，直接输出false。...== 0) return false n /= 2 } return true }; 优化代码 const isPowerOfTwo = function(n) {...if (n < 1) return false while(n % 2 == 0) n /= 2 return n === 1 }; 位运算通过n & (n - 1) 是否为...因为一个数是2的幂次方，则这个2进制数必然只有一个1，若求x-1，则它的1位变为0，1后面的0位变为1，在求与运算，这是值为0。

9690 0

jdk源码分析之HashMap--为什么初始容量是2的n次幂

数组的长度）建议为2的n次幂呢？...我们举几个例子，length1=3(奇数)，length2 = 6(偶数)，length3 = 16(2的n次幂)，那么对应的length-1二进制数组如下： ?...从以上例子中可知，奇数和偶数(非2的n次幂)，和任何key的hashcode按位与操作，总会有一些位置覆盖不到。...回到上述的indexFor方法中，也就是说对于数组长度非2的n次幂的情况，永远会有一些数组位置辐射不到，再换一个角度来说，这些场景中，我们永远无法将Entry数组利用率提高到100%。...最后我们可以得出结论，使用HashMap的时候建议指定的容量是2的n次幂(很多人习惯使用空构造器，默认容量16已经满足需求)，具体还需要考虑业务场景而定。

4761 0

为什么hashMap的容量是2的幂次

HashMap通过哈希算法得出哈希值之后，将键值对放入哪个索引的方法 static int indexFor(int h, int length) { // assert Integer.bitCount...(length) == 1 : "length must be a non-zero power of 2"; return h & (length-1); } 假设 HashMap...的容量为16转化成二进制为10000，length-1得出的二进制为01111 哈希值为1111 ?...可以得出索引的位置为15 ---- 假设 HashMap的容量为15转化成二进制为1111，length-1得出的二进制为1110 哈希值为1111和1110 ?...那么两个索引的位置都是14，就会造成分布不均匀了，增加了碰撞的几率，减慢了查询的效率，造成空间的浪费。总结：因为2的幂-1都是11111结尾的，所以碰撞几率小。

1.6K5 0

为什么HashMap默认初始容量为2次幂？不是2次幂会怎样？讲讲 HashMap 扰动函数？

关于HashMap的详解文章请移步：链接: HashMap源码研究——源码一行一行的注释文章目录为什么初始容量是 2次幂？如果指定了不是2的次幂的容量会发生什么？...为什么初始容量是 2次幂？...那容量不是 2次幂会怎么样？我们来做个试验。...2次幂的情况：非2次幂的情况，假设 n = 10: 对比来看，哪种发生哈希碰撞的概率更低一目了然，如果 n 为 2次幂，可以保证数据的均匀插入，降低哈希冲突的概率，毕竟冲突越大，代表数组中的链表...如果指定了不是2的次幂的容量会发生什么？

1.3K2 1

HashMap 容量为什么总是为 2 的次幂？

为什么要保证 capacity 是2的次幂呢？ 1）在get方法实现中，实际上是匹配链表中的 Node[] tab 中的数据。...2）因为 n 永远是2的次幂，所以 n-1 通过二进制表示，永远都是尾端以连续1的形式表示（00001111，00000011）当(n - 1) 和 hash 做与运算时，会保留hash中后 x...- 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n 2.为什么要通过 (n - 1) & hash 决定桶的索引呢？...0 : (h = key.hashCode()) ^ (h >>> 16); } 3.capacity 永远都是 2 次幂，那么如果我们指定 initialCapacity 不为 2次幂时呢，是不是就破坏了这个规则...答案是：不会的，HashMap 的tableSizeFor方法做了处理，能保证n永远都是2次幂。

2.1K2 0

LeetCode | 2 的幂

LeetCode 题库的第 231 题 —— 2 的幂 ? 这题也是比较容易的一题，前提是找到规律即可。...如果从 10 进制的角度观察 2 的幂次方，可能并不容易发现规律，那么可以从 2 进制的角度进行观察。...举例如下： 2 = 2 ^ 1 = 10 4 = 2 ^ 2 = 100 8 = 2 ^ 3 = 1000 16 = 2 ^ 4 = 10000 观察 2 进制可以看出，2 的 N...的幂，直接返回 0，num 必须要大于 1，否则直接返回 1，因为当 num 等于 1 时要么是循环结束，要么 num 本身就是 1，如果是 1 的话，就是 2 的 0 次幂。...就直接返回一个 0，如果循环中 num 的最低位都不为 1，那么最后就返回 1 即可。整个过程其实很简单，如果不太明白，那么最简单的方式就是将一个值转换为 2 进制，跟着调试一次即可。

6002 0

LintCode x的n次幂题目分析代码

题目实现 pow(x,n) 注意事项不用担心精度，当答案和标准输出差绝对值小于1e-3时都算正确样例 Pow(2.1, 3) = 9.261 Pow(0, 1) = 0 Pow(1, 0)...递归的主体部分 */ // X^(-n) = X^(n + 1) * X // X^n = 1/(x^(-n)) if...(n < 0) { double ret = x * myPow(x, -(n + 1)); return (double)1/ret;...再将结果相乘 double ret = myPow(x, n / 2); ret = ret * ret; //如果有余数，再乘以x本身...if (n % 2 != 0) { ret = ret * x; } return ret; } }

5772 0

Batch大小不一定是2的n次幂！ML资深学者最新结论

羿阁编译整理量子位 | 公众号 QbitAI Batch大小不一定是2的n次幂？是否选择2的n次幂在运行速度上竟然也相差无几？有没有感觉常识被颠覆？...在介绍他的试验方法之前，首先来回顾一下这个惯例究竟是怎么来的？ 2的n次幂从何而来？一个可能的答案是：因为CPU和GPU的内存架构都是由2的n次幂构成的。...△由于GPU内存限制，无法使用大于515的样本数量可以看出，跟上一轮结果一样，不管样本数量是否是2的n次幂，训练速度的差异几乎可以忽略不计。...正如我们看到的，2的n次幂（256）的运行速度并不比255差太多。...结论可以看出，选择2的n次幂或8的倍数作为batch大小在实践中不会产生明显差异。然而，由于在实际使用中已成为约定俗成，选择2的n次幂作为batch大小，的确可以帮助运算更简单并且易于管理。

8251 0

LintCode-142.O(1)时间检测2的幂次

题目描述用 O(1) 时间检测整数 n 是否是 2 的幂次。样例 n=4，返回 true; n=5，返回 false. 解答思路大于零。...2的整数幂次的二进制表示都是0...010...0，其减1后二进制表示为0...001...1，两个数按位取且（&）等于零。...代码 class Solution { /* * @param n: An integer * @return: True or false */ public...boolean checkPowerOf2(int n) { // write your code here return (n>0)&&((n&(n-1))==0);

5603 0

231. 2的幂

链接给定一个整数，编写一个函数来判断它是否是 2 的幂次方。...示例 1: 输入: 1 输出: true 解释: 20 = 1 示例2: 输入: 16 输出: true 解释: 24 = 16 示例 3: 输入: 218 输出: false 题解 func...isPowerOfTwo(n int) bool { return n > 0 && (n & (n-1) == 0) }

4.4K0 0

231. 2的幂

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。...不管是2的正幂次还是2的负幂次肯定都大于0，如果n小于0可以直接返回false，2的负幂次如2^-3等价于1/2^3一定是小数，由于入参为int所以这种情况也不存在。...2的幂次十进制形式二进制形式减1二进制形式 2 ^ 0 1 00000001 00000000 2 ^ 1 2 00000010 00000001 2 ^ 2 4 00000100 00000100...n - 1)) == 0); } } 解2： class Solution { public boolean isPowerOfTwo(int n) { //return...= 1) { if (n % 2 == 1) { return false; } n /= 2;

4761 0

2 的幂(C++)

2 的幂难度简单540收藏分享切换为英文接收动态反馈给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。...如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。...示例 1：输入： n = 1 输出： true 解释： 20 = 1 示例 2：输入： n = 16 输出： true 解释： 24 = 16 示例 3：输入： n = 3 输出： false 示例...: bool isPowerOfTwo(int n) { // n - 1就是把n的二进制位的最右边的那个1去掉如果这个时候去掉了最右边的那个1 // 这个还是很妙的...如果n真的是2的幂的话应该是这种形式 100000... // 这个数字和n-1的&一定是0 return n > 0 && (n & (n - 1)) == 0;

1720 0

8758:2的幂次方表示

8758:2的幂次方表示查看提交统计提问总时间限制: 1000ms 内存限制: 65536kB描述任何一个正整数都可以用2的幂次方表示。...例如： 137=27+23+20 同时约定方次用括号来表示，即ab可表示为a(b)。...输出一行，符合约定的n的0，2表示（在表示中不能有空格）。...{ 14 printf("2");// 2的一次方 15 return; 16 } 17 else 18 { 19 int...=0) 36 { //如果n分解之后还有剩余的数，那么继续分解 37 printf("+"); 38

1.9K6 0

Leetcode 231. 2的幂

题目描述给定一个整数，编写一个函数来判断它是否是 2 的幂次方。示例 1: 输入: 1 输出: true 解释: ?...= 1 示例 2: 输入: 16 输出: true 解释: ?...= 16 示例 3: 输入: 218 输出: false 解法如果该值是 2 的幂次方，则该值的二进制位中只有一位为 1，其他位全部为 0，则有 num&(num-1)==0。...class Solution(object): def isPowerOfTwo(self, n): """ :type n: int :rtype...: bool """ if n<=0: return False return n&(n-1)==0

4952 0

HashMap中数组的长度为什么要设计成2次幂?

HashMap中数组的长度为什么要设计成2次幂? 了解本文的前提需要你对数据结构有一定的了解，明白各种数据结构的优劣。当然如果你已经知道了HashMap底层的数据结构是数组+链表+红黑树那就更好了。...for(int n : length){ System.out.println("--------------"+n+"-----------------");...for(int hash=0;hash<=100;hash++){ System.out.print((hash & n-1)+"\t"); }...我们从map中取数据时，本来可以直接通过key计算出的槽位取出对应元素就可以了，现在因为这个槽位存放的是一个链表，那么想要取数据还得遍历这个链表，在非常极端的情况下（所有元素的hashcode都是相同的...这样就失去了数组随机查找效率高的这样一个特性。因此让数组的长度等于二次幂可以有效的减少hash冲突的概率。 HashMap还有许多的特性，感兴趣的话可以参考JDK自己手写一个HashMap。

1.1K2 0

LeetCode231. 2的幂

2的幂从小到大有1，2，4，8... ...观察他们的二进制：1 = 1，2 = 10，4 = 100，8 = 1000......我们发现2的幂基本上都满足这样一个规律就是，这个数的二进制数都是1开头，后面m个0 我们再看一下每个2的幂次方数减...1：0 = 0，1 = 1，3 = 011，7 = 0111......我们发现正好每一位都是与2的幂的二进制相反，于是我们可以将n和n-1相&，得到的结果如果是0，就表示n是2的幂，如果不是0，他就不是...2的幂 class Solution { public boolean isPowerOfTwo(int n) { if(n <= 0) return false...; return ((n & (n - 1)) == 0); } }

3991 0

点击加载更多

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭