C语言 操作整数型数据变量的最右/最左n位,而不是所有位

qlvxas9a  于 2022-12-11  发布在  其他
关注(0)|答案(2)|浏览(123)

在编程任务中,我必须在变量B(数据类型int)中添加一个较小的整数
变量A(数据类型long long int)中的较大整数(20十进制整数),
然后将A与变量C进行比较,变量C也是与A一样大整数(数据类型long long int)。
我意识到,既然我把一个较小的B加到A上,
在与C进行比较时,我不需要检查A的所有位,换句话说,我们不需要检查AC的所有位。
假设我知道,我需要检查右边的多少位,比如n位,
是否有一种方法/技术可以只检查从右边开始的特定n位(而不是A、C的所有位),以使c编程语言中的程序更快?
因为比较所有的位需要更多的时间,而且因为我在处理大量的数字,程序变得更慢。每次我在谷歌搜索,位掩码出现,使用A, C的所有位,这不做我所要求的,所以可能我没有使用正确的术语,请帮助。

增加:
这篇文章的最初评论让我觉得没有办法,但我发现以下内容-

Bit Manipulation by University of Colorado Boulder (@cuboulder, after 7:45)
......通过位带别名访问位带区域,所支持的位带区域中的每个位都具有其自己的唯一地址,并且我们可以使用指向其位带别名位置的指针来访问该位,别名位置中的最低有效位可以被发送或清除,并且将被Map到相应数据或外围存储器中的位,不幸的是,这将不会帮助你,如果你需要写到多个位的位置,在内存相关的操作只允许一个单一的位被清除或设置...
以上是我的要求吗?如果是,那么作为初学者,我在哪里可以找到细节?
更新问题:
是否有一种方法/技术可以只检查从右边开始的特定n位(而不是A、C的所有位),以使c编程语言(或任何其他语言)中的程序更快?

oxiaedzo

oxiaedzo1#

您认为比较更少的位更快的假设在某些情况下可能是正确的,但在大多数情况下可能不是正确的。
我只熟悉x86 CPU。x86-64处理器有64位宽的寄存器。这些寄存器可以作为64位寄存器访问,但较低的位也可以作为32、16和8位寄存器访问。有处理器指令与寄存器的64、32、16或8位部分一起工作。比较8位是一条指令,比较64位也是一条指令。
如果使用32位比较比64位比较更快,您可以获得一些速度。但似乎当前处理器代之间没有速度差异。(请查看“cmp”指令,其中包含@harold的uops.info链接。)
如果long long数据类型实际上大于处理器的字长,则情况就不同了。例如,如果long long是64位,但处理器是32位,则这些指令不能由一个寄存器处理,需要多个指令。因此,如果您知道仅比较较低的32位就足够了,则可以保存一些时间。
还要注意,只比较20位实际上比比较32位要花更多的时间。你必须比较32位,然后屏蔽12个最高位。所以你需要一个比较和一个按位and指令。
正如你所看到的,这是非常特定于处理器的。你是在处理器的操作码级别上。正如@RawkFist在他的评论中所写的,你可以尝试让C编译器创建这样的指令,但这并不意味着这会更快。
所有这些操作只有在这些操作被执行很多次的情况下才有意义。我不知道你在做什么。例如,如果你把很多值B加到A上,每次都把它们和C比较,从C开始可能会更快。从其中减去B值,然后与0进行比较。因为compare-运算的内部工作方式与减法类似。因此,在循环中,一条subtraction指令就足够了,而不是一条add和一条compare指令。但是,现代CPU和编译器非常智能,并且进行了大量优化。因此,编译器可能会自动执行此类或类似的优化。

ecbunoof

ecbunoof2#

试试这个问题。
有没有一种方法/技术可以只检查从右边开始的特定n位(而不是A、C的所有位),以使程序在c编程语言(或任何其他语言)中运行得更快?
是-当A + B != C时。一旦发现差异,我们可以简化比较:从最低有效位到最高有效位。
否-当A + B == C.所有位都需要比较。
现在回到OP最初的问题
有没有一种方法/技术可以只检查从右边开始的特定n位(而不是A、C的所有位),以使程序在c编程语言(或任何其他语言)中更快
不。为了做到这一点,我们需要超越编译器。一个功能良好的编译器本身会注意到long long + (signed char)int == long long的任何“技巧”,并发出有效的代码。
那么,对于AC的定制uint1000000呢?
对于自定义类型的 long 比较,可以进行快速比较。
首先,选择一个快速工作类型。unsigned是首选。

typedef unsigned ufast;

现在定义 wide 整数。

#include <limits.h>
#include <stdbool.h>
#define UINT1000000_N (1000000/(sizeof(ufast) * CHAR_BIT))

typedef struct {
  // Least significant first
  ufast digit[UINT1000000_N];
} uint1000000;

执行加法并每次比较一个“数字”。

bool uint1000000_fast_offset_compare(const uint1000000 *A, unsigned B,
    const uint1000000 *C) {
  ufast carry = B;
  for (unsigned i = 0; i < UINT1000000_N; i++) {
    ufast sum = A->digit[i] + carry;
    if (sum != C->digit[i]) {
      return false;
    }
    carry = sum < A->digit[i];
  }
  return true;
}

相关问题