gpt4 book ai didi

Java - bitCount() 的大 O?

转载 作者:行者123 更新时间:2023-12-01 07:48:26 26 4
gpt4 key购买 nike

位计数的 Big O 是多少?我不确定该方法是如何工作的,但我假设它是在 O(logn) 中完成的。

具体来说,使用此代码(其中 x = 4,y = 1):

return Integer.bitCount(x^y);

最佳答案

鉴于其实现,该方法由按顺序执行的 6 个 O(1) 语句组成,因此它的复杂度为 O(1)。

public static int bitCount(int i) {
// HD, Figure 5-2
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}

关于Java - bitCount() 的大 O?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44250311/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com