标签: bit-packing

低级别位操作从来都不是我的强项.我将理解一些有助于理解按位运算符的以下用例.考虑...

int age, gender, height, packed_info;

. . .   // Assign values 

// Pack as AAAAAAA G HHHHHHH using shifts and "or"
packed_info = (age << 8) | (gender << 7) | height;

// Unpack with shifts and masking using "and"
height = packed_info & 0x7F;   // This constant is binary ...01111111
gender = (packed_info >> 7) & 1;
age    = (packed_info >> 8);

我不确定这段代码是什么以及如何完成的？为什么使用幻数0x7F？如何完成包装和拆包？

资源

我有8个bool变量,我想将它们"合并"成一个字节.

有一个简单/首选的方法来做到这一点？

相反,如何将一个字节解码为8个独立的布尔值？

我认为这不是一个不合理的问题,但由于我无法通过谷歌找到相关文档,它可能是另一个"非你所有直觉都是错误的"案例.

在代码审查期间,我遇到了一些定义简单结构的代码,如下所示:

class foo {
   unsigned char a;
   unsigned char b;
   unsigned char c;
}

在其他地方,定义了这些对象的数组:

foo listOfFoos[SOME_NUM];

之后,将结构原始复制到缓冲区中:

memcpy(pBuff,listOfFoos,3*SOME_NUM);

此代码依赖于以下假设:a.)foo的大小为3,并且不应用填充,并且b.)这些对象的数组被打包,它们之间没有填充.

我已经在两个平台(RedHat 64b,Solaris 9)上使用GNU进行了尝试,并且它在两者上都有效.

以上假设是否有效？如果没有,在什么条件下(例如OS /编译器的变化)可能会失败？

我有一个整数数组,让我们假设它们是类型int64_t.现在,我知道n每个整数的每个第一位都是有意义的(也就是说,我知道它们受到某些界限的限制).

以所有不必要的空间被移除的方式转换数组的最有效方法是什么(即我有第一个整数a[0],第二个是a[0] + n bits等等)？

我希望它尽可能地通用,因为它n会不时变化,但我想可能会对n2或者某些特定功能进行智能优化.

当然我知道我可以只重复价值超过价值,我只想问你StackOverflowers你是否能想到更聪明的方式.

编辑:

这个问题不是关于压缩数组以尽可能减少空间.我只需n bits要从每个整数"切割" 并给出数组,我知道n我可以安全切割的位的确切位置.

我正在尝试在C#中优化解析器组合器.当序列化格式与内存格式匹配时,一种可能的优化是仅对要在实例上解析的数据的(不安全)memcpy或甚至该类型的许多实例进行解析.

我想编写代码来确定内存中的格式是否与序列化格式匹配,以便动态确定是否可以应用优化.(显然这是一个不安全的优化,可能无法解决一大堆微妙的原因.我只是在尝试,而不是计划在生产代码中使用它.)

我使用属性[StructLayout(LayoutKind.Sequential,Pack = 1)]强制不填充并强制内存顺序匹配声明顺序.我用反射检查该属性,但实际上所有这些都证实是"无填充".我还需要字段的顺序.(我非常希望不必为每个字段手动指定FieldOffset属性,因为这样很容易出错.)

我假设我可以使用GetFields返回的字段顺序,但文档明确指出订单未指定.

鉴于我使用StructLayout属性强制字段的顺序,有没有办法反映该排序？

编辑我很好,所有字段必须是blittable的限制.

更新:这被称为de Brujin torus,但我仍需要在C#中找出一个简单的算法.

http://en.wikipedia.org/wiki/De_Bruijn_torus

http://datagenetics.com/blog/october22013/index.html

我需要尽可能密集地组合3x3位网格的所有值.通过一个3x3位网格,我的意思是一个3x3网格,其中每个地方有点类似于这个问题中的打孔概念:

找到3x3打孔的所有组合

3x3位网格示例:

XXX .X. ...
XXX .X. .X.
XXX .X. ...

目标

我想打包所有512(实际上256,因为中心位始终打开)可能的值,以便它们在单个NxM网格中重叠.

不完整的例子:

此示例将~25个可能值打包到7x7网格中.

.......
.X.XXX.
.......
.X.XXX.
.X.XXX.
.X.XXX.
.......

已知的事情:

• 有2 ^ 9(512)个唯一值.
• 我只关心2 ^ 8(256)个值,因为我需要始终打开中心位.

尝试

我手动尝试了许多不同的技术,但无法提出简单的算法.

所以,我想写一个C#程序来创建它,但我也没有看到一个简单的方法.

对我来说,甚至没有一种明显的蛮力方法.似乎任何暴力尝试都会接近512!在更坏的情况下组合.

意见

每条边只有8个可能的值.

X...X.XXX. //(8+2 bits) Exhausts all values in the same problem with 1-Dimension.

.X.XXX.    //(5+2 bits) The above simplifies when the center bit must be on. 

目的

这实际上将用于基于2d拼图的游戏.

游戏中有N个可能的碎片.鉴于地面可以在任何情况下发生,设计师需要一种方法来表达应该针对任何给定情况选择哪个区块.

包含所有可能情况的紧凑网格是指定在每种情况下使用哪个磁贴并消除所有冗余的最有效方法.

更新

例

....
.XX.
.XX.
....

以上是允许表达4种情况的基本模式,我将修改它以使用其他ascii值来表示应在每种情况下使用的结果:

....
.AG.
.HH. …

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

#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)

{ …

我正在创建一个PackedUnsigned1616类,它在一个int中存储两个unsigned short,以及一个PackedSigned1616类,它在一个int中存储两个带符号的short.我已经阅读了按位运算,但我仍然对如何处理有符号和无符号以及大于或小于short的范围(它们作为两个整数传入)的值感到困惑.这是我到目前为止所得到的:

public final class PackedUnsigned1616 {
public final int field;

private static final int RIGHT = (2 << 15) - 1;
private static final int LEFT = ((2 << 31) - 1) ^ RIGHT;

public PackedUnsigned1616(int left, int right) {
    field = (left << 15) | (right & RIGHT);
}

public int getLeft() {
    return field >> 15;
}
public int getRight() {
    return field & RIGHT;
}

}

整个概念让我很困惑,所以如果你能对它有所了解,那将会有很大的帮助.

具有位域的结构，即使在“打包”时，似乎也会根据指定的 int 类型来处理位域的大小（以及对齐方式？）。有人可以指出定义该行为的 C++ 规则吗？我尝试了十几个编译器和体系结构（谢谢你，编译器资源管理器！），结果在所有编译器和体系结构中都是一致的。

这是要使用的代码： https: //godbolt.org/z/31zMcnboY

#include <cstdint>

#pragma pack(push, 1)
struct S1{ uint8_t  v: 1; }; // sizeof == 1
struct S2{ uint16_t v: 1; }; // sizeof == 2
struct S3{ uint32_t v: 1; }; // sizeof == 4
struct S4{ unsigned v: 1; }; // sizeof == 4
#pragma pack(pop)

auto f(auto s){ return sizeof(s); }

int main(){
    f(S1{});
    f(S2{});
    f(S3{});
    f(S4{});
}

生成的 ASM 清楚地显示了、 的返回大小分别f()为 1、2、4 ：S1S2 …

我正在研究一个基于TCP的应用程序来处理比特包消息,这意味着:发送/接收的消息不是字节对齐的.例如,3比特表示字段1,其中19比特可以表示字段2.我的问题是,是否有人知道可以采用一组字节并在这些字节内设置/获取任意比特范围的C#库？我已经看到并在C/C++中创建了类似的实用程序,但我需要一个100%的C#解决方案,我不想再次重新发明轮子.

我查看了BitArray类,但它不允许引用任意比特范围.