标签: bit-fields

当我想要同时计算两个集合(存储为列表)的并集和交集以及差异时,我[当然重新]发明了这个[wheel].初始代码(不是最严格的):

dct = {}
for a in lst1:
  dct[a] = 1
for b in lst2:
  if b in dct:
    dct[b] -= 1
  else:
    dct[b] = -1

union = [k for k in dct]
inter = [k for k in dct if dct[k] == 0]
oneminustwo = [k for k in dct if dct[k] ==  1]
twominusone = [k for k in dct if dct[k] ==  -1]

然后我意识到我应该使用00,01,10和11而不是-1,1,0,......所以,位置n处的位表示集合n中的成员资格.

这可以使用32位int推广到最多32个集合,或使用bitarray或字符串推广到任意数量的集合.因此,您预先计算此字典一次,然后使用非常快速的O(n)查询来提取感兴趣的元素.例如,所有1都表示所有集合的交集.所有0都是特殊的 - 不会发生.

无论如何,这不是为了自己的号角.这肯定是以前发明的并且有一个名字.这叫什么？这种方法是在数据库中使用的吗？

我在C中有一个8位的标志,我想使用这样的位字段逐位访问它:

#include <stdio.h>
#include <stdint.h>

int main(void) {
    struct flags{
        uint8_t bits1:1;
        uint8_t bits2:1;
        uint8_t bits3:1;
        uint8_t bits4:1;
        uint8_t bits5:1;
        uint8_t bits6:1;
        uint8_t bits7:1;
        uint8_t bits8:1;
    };
    struct flags *my_flags;
    uint8_t x=6,i;

    my_flags=(struct flags *)&x;
    printf("%u\t",my_flags->bits5);
    printf("%u\t",my_flags->bits6);
    printf("%u\t",my_flags->bits7);
    printf("%u\t",my_flags->bits8);
    printf("%u\t",my_flags->bits1);
    printf("%u\t",my_flags->bits2);
    printf("%u\t",my_flags->bits3);
    printf("%u\t",my_flags->bits4);
    return 0;
}

我得到了预期的输出:0 0 0 0 0 1 1 0.

但这有点太多编码.

1. 是不是像位字段数组或任何其他解决方法？(要么)
2. 在C my_flags->bits_i中有什么类似的东西,i它将成为循环中的计数器吗？

我知道默认情况下两者都不存在.但有没有其他方法可以实现相同的目标？

我即将实施Eratosthenes筛,并对筛阵有一个普遍的问题.

我现在已经实施了几次筛子(在C中),并且总是使用一组uint8_t(外<stdint.h>)作为筛子.这是非常低效的内存,因为每个数字都使用8位来筛选,即使一位应该足够.

我怎么会用C来解决这个问题呢？我需要一个位数组.我可以几乎创建任何类型的(阵列uint8_t,uint16_t,uint32_t,uint64_t),并与比特掩码等访问单个位

我应该选择哪种数据类型以及在没有性能损失的情况下应该使用哪些操作来访问这些位？

PS:我不认为这是一个重复的只是一个BitArray实现,因为它的问题是具体的关于埃拉托色尼的筛,因为它的主要性质必须是有效的(不仅在内存使用情况,但在访问).我在想,也许可以使用不同的技巧来使筛分过程更有效...

为了澄清我的问题,让我们从一个示例程序开始:

#include <stdio.h>

#pragma pack(push,1)
struct cc {
    unsigned int a   :  3;  
    unsigned int b   : 16;
    unsigned int c   :  1;
    unsigned int d   :  1;
    unsigned int e   :  1;
    unsigned int f   :  1;
    unsigned int g   :  1;
    unsigned int h   :  1;
    unsigned int i   :  6;  
    unsigned int j   :  6;  
    unsigned int k   :  4;  
    unsigned int l   : 15;
};
#pragma pack(pop)

struct cc c;

int main(int argc, char **argv)

{ …

我有一个问题,我有点困惑,一位同事告诉我,这将是一个寻求帮助的好地方.

我试图在Java中实现C风格的位域.这是一个粗略的例子(此时我没有在我面前的实际代码).

typedef union
{
  typedef struct
  {
     unsigned short a :1;
     unsigned short b :1;
     unsigned short c :2;
     unsigned short d :10;
  } bitfield;

  unsigned short bitmap;
}example_bitfield;

遗留代码中我有一些类似的样式位域.我需要为Java提供等效方法的原因是我正在研究将使用Java与使用UDP的其他遗留应用程序进行通信的代码.

我没有重写代码的选项.我知道这种方法不可移植,有字节序问题(和填充/对齐等),如果我能够重写代码,可以做得更好.不幸的是,我需要回答这个非常具体的问题.系统已关闭,因此我不需要担心编译器/操作系统等每一种可能的组合.

使用Java EnumSet的方法不起作用,因为我认为只允许每个值为一位.我需要能够打包值,例如占用10位的d值.

我知道Java Bitset但它有局限性.我使用的是旧版本的Java,因此我没有一些较新的Java Bitset方法(即可能肯定有帮助的valueOf方法).

有没有人有任何关于如何使这个尽可能易于管理的想法？我有超过10个位域需要为我的通信实现.

感谢您提供任何帮助!

我有这个C结构:(代表一个IP数据报)

struct ip_dgram
{
    unsigned int ver   : 4;
    unsigned int hlen  : 4;
    unsigned int stype : 8;
    unsigned int tlen  : 16;
    unsigned int fid   : 16;
    unsigned int flags : 3;
    unsigned int foff  : 13;
    unsigned int ttl   : 8;
    unsigned int pcol  : 8;
    unsigned int chksm : 16;
    unsigned int src   : 32;
    unsigned int des   : 32;
    unsigned char opt[40];
};

我正在为它赋值,然后以16位字打印它的内存布局,如下所示:

//prints 16 bits at a time
void print_dgram(struct ip_dgram dgram)
{ …

我在C中有一个压缩结构,我想在Python中解析.我注意到sizeofC(使用GCC 4.9.2)和Python 3.4.2中的ctypes库之间的运算符返回的结构大小与位域的差异.

以下C代码按预期打印5:

#include <stdio.h>
#include <stdint.h>

typedef struct __attribute__((packed)) {
    uint32_t ch0 : 20;
    uint32_t ch1 : 20;
} pkt_t;

int main(){
    printf("sizeof(pkt_t): %d\n", sizeof(pkt_t));
    return 0;
}

虽然Python中的(相同)代码打印8

import ctypes

class Packet(ctypes.LittleEndianStructure):
    _pack_ = 1
    _fields_ = [
        ('ch0', ctypes.c_uint32, 20),
        ('ch1', ctypes.c_uint32, 20),
    ]   

print(ctypes.sizeof(Packet()))

看起来它_pack_ = 1等同__attribute__((aligned(1)))于C,而不是__attribute__((packed, aligned(1)))使结构尽可能紧密地打包.有没有办法packed为ctypes结构启用属性？

细节

cppreference中位字段的引用提供了以下示例:

#include <iostream>
struct S {
 // three-bit unsigned field,
 // allowed values are 0...7
 unsigned int b : 3;
};
int main()
{
    S s = {7};
    ++s.b; // unsigned overflow (guaranteed wrap-around)
    std::cout << s.b << '\n'; // output: 0
}

Run Code Online (Sandbox Code Playgroud)

强调保证环绕评论.

但是,WG21 CWG Issue 1816描述了一些可能的问题,即位字段值的规范不清楚,以及最新标准草案规则中的[expr.post.incr]/1:

后缀++表达式的值是其操作数的值....

如果操作数是不能表示递增值的位字段,则位字段的结果值是实现定义的.

但是,如果这也适用于无符号位域的环绕,我不确定.

题

• 无符号位字段溢出是否保证环绕？

我在签名位域上遇到了一个奇怪的行为：

#include <stdio.h>

struct S {
    long long a31 : 31;
    long long a32 : 32;
    long long a33 : 33;
    long long : 0;
    unsigned long long b31 : 31;
    unsigned long long b32 : 32;
    unsigned long long b33 : 33;
};

long long f31(struct S *p) { return p->a31 + p->b31; }
long long f32(struct S *p) { return p->a32 + p->b32; }
long long f33(struct S *p) { return p->a33 + p->b33; }

int main() { …

为什么这两个结构体的大小不同？

#pragma pack(push, 1)
    struct WordA
    {
        uint32_t address           : 8;
        uint32_t data             : 20;
        uint32_t sign              : 1;
        uint32_t stateMatrix : 2;
        uint32_t parity            : 1;
    };

    struct WordB
    {
        uint8_t address;
        uint32_t data             : 20;
        uint8_t sign              : 1;
        uint8_t stateMatrix : 2;
        uint8_t parity            : 1;
    };
#pragma pack(pop)

不知何故WordB占用 6 个字节而不是 4 个，而WordA正好占用 32 位。我假设给定结构内使用位的总和会使两个结构具有相同的大小。显然我错了，但我找不到原因的解释。 位字段页面仅显示所有结构成员都属于同一类型时的示例，这是一种情况WordA.

任何人都可以解释一下，为什么尺寸不匹配，以及它是否符合标准或实现定义？