标签: bitarray

我正在学习C/C++编程并遇到过"位数组"或"位向量"的用法.我无法理解他们的目的？这是我的疑惑 -

1. 它们是否用作布尔标志？
2. 可以使用int数组吗？(当然更多的记忆,但..)
3. 这个Bit-Masking的概念是什么？
4. 如果位掩码是简单的位操作以获得适当的标志,那么如何为它们编程？是不是很难在脑袋里做这个操作,看看标志会是什么,与十进制数相对应？

我正在寻找应用程序,以便我能更好地理解.对于Eg -

问:您将获得一个包含范围内的整数(1到1百万)的文件.有一些重复,因此缺少一些数字.找到找到丢失数字的最快方法？

对于上面的问题,我已经阅读了告诉我使用位数组的解决方案.如何将每个整数存储一下？

我过去必须多次这样做,而且我从未对结果感到满意.

任何人都可以建议一种快速的方法从源到目的地复制连续的位阵列,其中源和目标可能没有在方便的处理器边界上对齐(右移)？

如果源和目标都没有对齐,问题很快就会变成一个只有一个没有对齐的问题(在第一个副本之后说).

作为一个起点,我的代码不可避免地最终看起来像下面这样(未经测试,忽略副作用,这只是一个关闭袖口的例子):

const char mask[8] = { 1, 3, 7, 15, 31, 63, 127, 255 };
/* Assume:
 * - destination is already zeroed,
 * - offsets are right shifts
 * - bits to copy is big (> 32 say)
 */
int bitarray_copy(char * src, int src_bit_offset, int src_bit_len,
                  char * dst, int dst_bit_offset) {
    if (src_bit_offset == dst_bit_offset) { /* Not very interesting */ 
    } else {
        int bit_diff_offset = src_bit_offset - dst_bit_offset; /* assume positive */ …

我有一个System.Collections.BitArray数组(~3000项),我想将所有位向左移动1.然而,该集合似乎不支持该操作(即bitArray << 1不工作,那里不是方法).有关如何做到这一点的任何想法？

谢谢!

我正在设计一个bloom过滤器,我想知道Python中性能最高的位数组实现是什么.

Python的优点是它可以处理开箱即用的任意长度整数,这就是我现在使用的,但我不太了解Python内部,知道这是否是在Python中执行它的最高性能方式.

我找到了,bitarray但它处理了很多其他的事情,比如切片,我不需要.我只需要&和|和<<操作.

我有一些代码管理从传感器阵列接收的数据.控制传感器的PIC使用8个SAR-ADC并行读取4096个数据字节.这意味着它读取前8个字节的最高有效位; 然后它读取它们的第二位,依此类推,直到第八位(最低位).
基本上,对于它读取的每8个字节,它创建(并向计算机发送)8个字节,如下所示:

// rxData[0] = MSB[7] MSB[6] MSB[5] MSB[4] MSB[3] MSB[2] MSB[1] MSB[0]
// rxData[1] = B6[7] B6[6] B6[5] B6[4] B6[3] B6[2] B6[1] B6[0]
// rxData[2] = B5[7] B5[6] B5[5] B5[4] B5[3] B5[2] B5[1] B5[0]
// rxData[3] = B4[7] B4[6] B4[5] B4[4] B4[3] B4[2] B4[1] B4[0]
// rxData[4] = B3[7] B3[6] B3[5] B3[4] B3[3] B3[2] B3[1] B3[0]
// rxData[5] = B2[7] B2[6] B2[5] B2[4] B2[3] B2[2] B2[1] B2[0]
// rxData[6] = B1[7] B1[6] B1[5] B1[4] B1[3] B1[2] B1[1] B1[0] …

我正在开发一个项目,我需要一些项目.我正在uint64_t为bitset 使用一个数组.

我目前的问题是,无论何时我想设置或检查一下,我都需要做这样的操作:

uint64_t index = 42;
bArr[index/64] |= (((uint64_t)1)<<(index%64)); 

我可以重写师,并与一些聪明的模与和位位移操作为好,但我担心的演员1.我需要这个演员,因为否则它1被视为32位单元.如本示例所示 - 如果没有强制转换,则输出错误:

uint64_t bArr[4];                           // 256 bits 
bArr[0] = bArr[1] = bArr[2] = bArr[3] = 0;  // Set to 0

uint64_t i = 255;
bArr[i/64] = (bArr[i/64] | (((uint64_t)1)<<(i%64))); 

uint32_t i2;
for (i2 = 0; i2 < 256; i2++) {
  if ((bArr[i2/64] & (((uint64_t)1)<<(i2%64))) != 0) {
    printf("bArray[%" PRIu32 "] = 1\n", i2);
  }
}

我能以聪明的方式绕过这个演员吗？我当时认为表演可能会受到每次读/写的影响......

我正在处理C++中非常大的布尔列表,每个约有2 ^ N个N布尔项.因为内存在这种情况下是关键的,即指数增长,我想构建一个N位长变量来存储每个元素.

对于小N,例如24,我只是使用unsigned long int.需要64MB((2 ^ 24)*32/8/1024/1024).但我需要上升到36.内置的变量是唯一的选择unsigned long long int,但它需要512GB((2 ^ 36)*64/8 /一千○二十四分之一千○二十四/ 1024),这是一个有点过分.使用36位变量,它可以为我工作,因为大小下降到288GB((2 ^ 36)*36/8/1024/1024/1024),这适合我的超级计算机的节点.

我试过std::bitset,但std::bitset< N >创造了至少8B的元素.所以列表std::bitset< 1 >远远大于列表unsigned long int.这是因为std::bitset只是改变了表示,而不是容器.

我也尝试过boost::dynamic_bitset<>Boost,但结果甚至最差(至少32B!),出于同样的原因.

我知道一个选项是将所有元素写为一个布尔链,2473901162496(2 ^ 36*36),然后存储在38654705664(2473901162496/64)unsigned long long int,它给出288GB(38654705664*64/8/1024/1024/1024).然后访问元素只是找到存储36位的元素的游戏(可以是一个或两个).但是现有代码(3000行)的重写很多,因为映射变得不可能,并且因为在某些功能执行期间添加和删除项目肯定会复杂,混乱,具有挑战性,结果很可能效率不高.

如何在C++中构建一个N位变量？

System.Collections.BitArray在我的应用程序中,我需要比类更多的东西.具体来说,我需要位数组:

• 是不可改变的
• 使用值语义实现相等性

我创建了自己的struct,主要是复制实现的内部BitArray.(谢谢,.Net Reflector!)

我不会每天处理按位操作,因此我对我的等式实现没有最高的信心.(它正在通过我投掷的单元测试,但我可能会遗漏边缘情况.)我将我提出的解决方案作为下面的答案.我会感谢别人的反馈和答案,可能更正确或更有效.

就像CLR一样BitArray,length字段指的是结构中的位数,array字段(或Array属性)指的是表示位的32位整数数组.

[澄清]我选择在构造函数和其他方法中采用简单的路径,这样我就不能依赖于不必要的位为零.例如,

• Not()是通过~整数数组元素上的按位取反()实现的.
• 可以使用构造函数,它使用length和boolean来初始化所有位.如果初始化值为true,我将int数组的所有元素设置为-1(以二进制补码表示,由全1表示)
• 等等.

因此,我需要在比较中处理(或者更确切地说,忽略)它们.一个好的解决方案也是在任何时候都将这些位置零,但在我的情况下会导致更多的工作(对于计算机和我来说都是如此!)

想象一下,您希望尽可能高效地(以二进制形式)对stackoverflow帖子(包括其标签)进行序列化和反序列化,以及在执行标记查找时的性能.这种情况是否有良好的数据结构？

Stackoverflow有大约28532个不同的标签,您可以创建一个包含所有标签的表并为它们分配一个整数.此外,您可以按频率对它们进行排序,以便最常见的标签具有最低的数字.从搜索和存储的角度来看,仍然将它们简单地存储为"1 32 45"格式的字符串似乎有点无穷无尽

另一个想法是将标签保存为变量bitarray,从查找和序列化的角度来看这是很有吸引力的.由于最常见的标签是第一个,您可能会将标签放入少量内存中.

问题当然是不常见的标签会产生巨大的比特.对于0的大跨度,是否有"压缩"比特阵列的标准？或者应该完全使用其他结构？

编辑

我不是在寻找一个数据库解决方案或解决方案,我需要将整个表保留在内存中,而是一个用于过滤单个项目的结构

我有一个像 temp = "0101110011" 这样的二进制数字符串，我想将它保存为文件，这个临时文件有 10 个字符，我如何将此字符串保存到 10 位长度的文件？

void Save_Data(string temp)
{
    bool[] BoolArray = new bool[temp.Length];
    BitArray Barray = new BitArray(BoolArray.Length);
    char[] ch = temp.ToCharArray();

    for (int i = 0; i < temp.Length; i++)
    {
        if (ch[i] == '0')
        {
            Barray[i] = false;
        }
        else
        {
            Barray[i] = true;
        }
    }

    Stream stream = new FileStream("D:\\test.dat", FileMode.Create);
    StreamWriter sw = new StreamWriter(stream);

    foreach (bool bit in Barray)
    {
        sw.Write(bit ? 1 : 0);
    }

    sw.Flush();
    sw.Close();
}

使用此代码，我的文件长度为 …