我使用以下函数来计算整数的log base 2:
public static int log2(int n){
if(n <= 0) throw new IllegalArgumentException();
return 31 - Integer.numberOfLeadingZeros(n);
}
它有最佳性能吗？
有人知道为此目的准备好J2SE API函数吗？
UPD1令 我惊讶的是,浮点算术似乎比整数算术更快.
UPD2 由于评论,我将进行更详细的调查.
UPD3 我的整数运算函数比Math.log(n)/Math.log(2)快10倍.
我将在离散结构中教授低级课程.我选择了教科书" 离散结构,逻辑和可计算性",因为它包含有助于使用函数式编程语言实现的示例和概念.(我也认为这是一本很好的教科书.)
我想要一个易于理解的FP语言来说明DS概念以及学生可以使用的.大多数学生最多只能用一到两个学期的Java编程.在查看Scheme,Erlang,Haskell,Ocaml和SML之后,我已经确定了Haskell或Standard ML.由于下面列出的原因,我倾向于Haskell,但我喜欢那些活跃的程序员在一个或另一个的意见.
从本质上讲,SML和Haskell大致相同.我倾向于Haskell,因为我喜欢Haskell中的列表理解和无限列表.但我担心Haskell紧凑语法中的大量符号可能会导致学生出现问题.从我收集到的关于SO的其他帖子开始,Haskell不建议初学者从FP开始.但我们不打算构建成熟的应用程序,只是尝试简单的算法.
你怎么看？
编辑:在阅读了一些很棒的回复后,我应该澄清一些我的要点.
在SML中,在解释器中定义函数和在外部文件中定义函数之间没有语法上的区别.假设您要编写阶乘函数.在Haskell中,您可以将此定义放入文件中并将其加载到GHCi中:
fac 0 = 1
fac n = n * fac (n-1)
对我来说,这很清楚,简洁,并且符合书中的数学定义.但是如果你想直接在GHCi中编写函数,你必须使用不同的语法:
let fac 0 = 1; fac n = n * fac (n-1)
在使用交互式口译员时,从教学角度来看,当学生在文件和命令行中使用相同的代码时,非常非常方便.
通过"显式确认函数",我的意思是在定义函数时,SML立即告诉您函数的名称,参数的类型和返回类型.在Haskell中你必须使用:type命令,然后你会得到一些有点令人困惑的咖喱符号.
关于Haskell的一个更酷的事情 - 这是一个有效的函数定义:
fac 0 = 1
fac (n+1) = (n+1) * fac n
同样,这与他们可能在教科书中找到的定义相匹配.在SML中无法做到这一点!
我面临一个相当特殊的问题.我正在研究一种不支持按位运算的体系结构的编译器.但是,它处理签名的16位整数算术,我想知道是否有可能只使用以下方式实现按位运算:
我希望能够支持的按位操作是:
discrete-mathematics bitwise-operators compiler-optimization
可能重复:
大Theta表示法 - 大Theta代表什么？
我认为,理论上我理解它,但我抓到的麻烦就是三者的应用.
在学校,我们总是使用Big O来表示算法的复杂性.例如,冒泡排序为O(n ^ 2).
现在,在阅读了更多理论之后,我认为Big Oh不是唯一的衡量标准,至少有两个其他有趣的标准.
但这是我的问题:
Big O是上限,Big Omega是下限,Big Theta是两者的混合.但这在概念上意味着什么呢？我明白它在图表上意味着什么; 我已经看过一百万个例子了.但它对算法复杂性意味着什么？"上限"或"下限"如何与之混合？
我想我只是没有得到它的应用程序.我理解,如果乘以一些常数c,如果在某个值n_0 f(x)之后大于g(x),则f(x)被认为是O(g(x)).但这实际意味着什么呢？为什么我们将f(x)乘以某个值c？天啊,我以为Big O符号倍数无关紧要.
生成一个列表列表(或打印,我不介意)一个大小为N 的Pascal三角形,代码可能最少!
这是我的尝试(使用技巧在python 2.6中的 118个字符):
c,z,k=locals,[0],'_[1]'
p=lambda n:[len(c()[k])and map(sum,zip(z+c()[k][-1],c()[k][-1]+z))or[1]for _ in range(n)]
说明:
[1][1]并制造[0,1]和[1,0][(0,1),(1,0)]并用sum来映射.用法(漂亮的打印,实际上是代码-golf xD):
result = p(10)
lines = [" ".join(map(str, x)) for x in result]
for i in lines:
print i.center(max(map(len, lines)))
输出:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 …algorithm code-golf combinatorics discrete-mathematics pascals-triangle
将两个二进制数相乘需要n ^ 2次,但是以某种方式可以更有效地对数字进行平方.(n是位数)这怎么可能？
还是不可能？这是精神错乱!
我正在查看条目在O(lg(N))操作中查找N位整数的日志基数2,并使用Bit Twiddling hacks 进行乘法和查找.
我可以很容易地看到该条目中的第二个算法是如何工作的
static const int MultiplyDeBruijnBitPosition2[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition2[(uint32_t)(v * 0x077CB531U) >> 27];
计算n = log2 v在哪里v知道2的幂.在这种情况下0x077CB531是一个普通的De Bruijn序列,其余的是显而易见的.
但是,该条目中的第一个算法
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 9, 1, 10, 13, 21, 2, …我正在尝试编写一段可以自动计算表达式的代码.例如,如果我有两个列表[1,2,3,4]和[2,3,5],代码应该能够找到两个列表中的公共元素,[2,3],并结合使用其余的元素在一个新的列表中,[1,4,5].
从这篇文章:如何找到列表交集？ 我看到可以找到共同的元素
set([1,2,3,4]&set([2,3,5]).
有一种简单的方法可以从每个列表中检索非公共元素,在我的例子中是[1,4]和[5]吗？
我可以继续做一个for循环:
lists = [[1,2,3,4],[2,3,5]]
conCommon = []
common = [2,3]
for elem in lists:
for elem in eachList:
if elem not in common:
nonCommon += elem
但这似乎是多余和低效的.Python是否提供了可以做到的任何方便的功能？提前致谢!!
根据维基百科,
树的高度是树中从根到最深节点的路径长度.只有一个节点(根)的(根)树的高度为零(或一).
我不明白 - 它是零还是一个(或两者)？
在我大学的算法和数据结构课程中,我收到了这个问题:
哪个整数与其负值具有相同的位模式？
意思是:x == -x
我知道0有效,但我怀疑教练正在寻找其他数字x.它是什么x？你怎么会找到它？