相关疑难解决方法(0)

我想写一个函数,返回最近的2个数的下一个幂.例如,如果我的输入是789,输出应该是1024.有没有任何方法可以实现这一点而不使用任何循环但只使用一些按位运算符？

我需要找到大于或等于给定值的2的最小幂.到目前为止,我有这个:

int value = 3221; // 3221 is just an example, could be any number
int result = 1;

while (result < value) result <<= 1;

它工作正常,但感觉有点幼稚.这个问题有更好的算法吗？

编辑.有一些很好的Assembler建议,所以我将这些标签添加到问题中.

什么是计算(long int) ceiling(log_2(i))输入和输出为6​​4位整数的快速方法？有符号或无符号整数的解决方案是可以接受的.我怀疑最好的方法将是一个类似于这里发现的方法,但不是尝试我自己,我想使用已经经过充分测试的东西.一般解决方案适用于所有正值.

例如,2,3,4,5,6,7,8的值为1,2,2,3,3,3,3

编辑:到目前为止,最好的路径似乎是使用任意数量的快速现有bithacks或寄存器方法计算整数/楼层日志基数2(MSB的位置),然后如果输入不是幂的话,则添加一个二.对2的幂的快速按位检查是(n&(n-1)).

编辑2:整数对数和前导零方法的一个很好的来源是亨利S.沃伦的Hacker's Delight中的第5-3和11-4节.这是我发现的最完整的治疗方法.

编辑3:这项技术看起来很有希望:https://stackoverflow.com/a/51351885/365478

是否有一行表达式(可能是布尔值)来获取2^n给定整数的最近数字？

示例:5,6,7必须为8.

对于给定的x < 10^15,迅速准确地确定的最大整数p,使得2^p <= x

以下是我尝试过的一些事情:

首先我尝试了这个,但对大数字来说并不准确:

>>> from math import log
>>> x = 2**3
>>> x
8
>>> p = int(log(x, 2))
>>> 2**p == x
True
>>> x = 2**50
>>> p = int(log(x, 2))
>>> 2**p == x #not accurate for large numbers?
False

我可以尝试类似的东西:

p = 1
i = 1
while True:
    if i * 2 > n:
        break
    i *= 2
    p += 1
    not_p = n - p …

常数是均匀分配60的幂的数字.例如,60 ² = 3600 = 48×75,因此48和75都是60的幂的除数.因此,它们也是常规数.

这是四舍五入到下一个幂的延伸.

我有一个整数值N,它可能包含大的素因子,我想把它四舍五入到只由小素因子组成的数字(2,3和5)

例子:

• f(18) == 18 == 21 * 32
• f(19) == 20 == 22 * 51
• f(257) == 270 == 21 * 33 * 51

找到满足此要求的最小数字的有效方法是什么？

涉及的值可能很大,所以我想避免枚举从1开始的所有常规数字或维护所有可能值的数组.

可能重复:
bit twiddling:找到下一个2的幂

如何获得给定数字的下一个2的幂？

例如,我收到号码138,下一个POT号码是256.

我收到112号,下一个POT是128.

我需要做一个计算它的算法

谢谢

我正在创建一个简单的支架系统,我需要一种方法来检查是否有正确数量的团队,或者如果我的程序需要补偿再见轮次.

现在,我正在使用此功能检查"两个权力":

function validBracket(data) {
    var x = data.teams.length;
    return ((x != 0) && !(x & (x - 1)));
}

这很好用,但我需要知道要添加多少个Bye轮.例如,如果我有16 teams,我就不需要再增加团队了.但是,如果我有12 teams,我需要第一个4 teams获得再见.

如何计算要添加到括号中的再见轮数？并且硬编码两个幂的数组会更好吗？

在伪代码中,我想到的是这样的东西:

if(validateBracket(data)) {
    // Valid number of teams (power of two). Keep going.
} else {
    var byeRounds = calculateByeRounds();
}

注意:我宁愿不使用如下两个幂的数组:

var powersOfTwo = [2,4,8,16,32,...];

这背后的原因是我会限制可以放入系统的团队数量(但是,我认为一个人不会超过256个团队).

我的问题由两部分组成.

1. 我注意到使用cc编译器在sparc(sun)上的memalign(block_size,bytes)不会检查字节是2的幂,而不是在intel linux上的memalign和使用mvsc编译器的windows上的_aligned_malloc检查字节是否为2的力量.

这是一个阳光下的虫子,有补丁还是我需要自己写一个memalign.

1. 另外我有一个结构(不是我的代码):

   typedef struct CLHLockStruct {
       volatile CLHLockNode CACHE_ALIGN *Tail ;
       volatile CLHLockNode CACHE_ALIGN *MyNode[N_THREADS] ;
       volatile CLHLockNode CACHE_ALIGN *MyPred[N_THREADS] ;
   } CLHLockStruct;
   

   Run Code Online (Sandbox Code Playgroud)

我在MVSC下编译(visual studio 2008):

    CACHE_LINE_SIZE = 64
    CACHE_ALIGN = __declspec(align(CACHE_LINE_SIZE)) 
    N_THREADS = 8
    sizeof(CLHLockStruct)=192

该代码最初是为sparc架构编写的,我尝试将其迁移到MVSC而无需更改代码.

在他们的代码中他们使用memalign(CACHE_LINE_SIZE,sizeof(CLHLockStruct)),并且我已将其更改为_aligned_malloc,我的问题是sizeof(CLHLockStruct)不是2的幂,我可能会写一些函数找到下一个数字是2的力量.

他们是更好的方法吗？

EDIT1

我如何填充这个结构,使其大小为2的幂？

EDIT2

是否有一个像_aligned_malloc和malloc一样的函数:返回一个与block_size的倍数对齐的内存指针,但不要求字节为2的幂？

如何有效地计算128位整数(uint128_t)中前导零的数量？

我知道GCC的内置功能:

• __builtin_clz,__builtin_clzl,__builtin_clzll
• __builtin_ffs,__builtin_ffsl,__builtin_ffsll

但是,这些函数仅适用于32位和64位整数.

我还发现了一些SSE指令:

• __lzcnt16,__lzcnt,__lzcnt64

正如您可能猜到的,这些仅适用于16位,32位和64位整数.

128位整数是否有类似的,高效的内置功能？

这是我的一般问题的后续行动: bit-twiddling-find-next-power-of-two

我现在创建了以下模板函数:

template <typename T>
T nextPowerOfTwo(T n)
{
    std::size_t k=1;
    n--;
    do {
        n |= n >> k ;
        k <<=1;
    }
    while (k < sizeof(T)*8)
    return ++n;
}

2个问题:

1. 指定T作为unsigned在nextPowerOfTwo(unsigned T n)抛出一个编译器错误.我可以以某种方式指定T是无符号的吗？
2. 有什么东西可以磨练优雅或表现明智吗？

编辑:纠正了代码,它开始是废话

编辑:再次更正了代码.真的对不起.实际上很明显.但无论如何,谢谢你的提示. 我想删除它,但已经有太多的贡献.

我想将以下 Matlab 代码转换为 C#：

nfft=2^nextpow2(nn);

其中NEXTPOW2(N)表示 Matlab 中 2 的下一个更高的幂。

那么我们如何自己用C#代码或者借助ilnumerics Lab来实现同样的功能呢？