当前位置： 文江博客话题详情

将位图旋转 90 度

发布于 2024-08-09 18:12:21 字数 634 浏览 2 评论 0原文

我有一个一个 64 位整数，我需要在 8 x 8 区域中将其旋转 90 度（最好使用直接位操作）。我无法找出任何方便的算法。例如，这样：

// 0xD000000000000000 = 1101000000000000000000000000000000000000000000000000000000000000

1 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

旋转后变成这样：

// 0x101000100000000 = 0000000100000001000000000000000100000000000000000000000000000000

0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

我想知道是否有任何解决方案不需要使用任何预先计算的哈希表？

原文

I have a one 64-bit integer, which I need to rotate 90 degrees in 8 x 8 area (preferably with straight bit-manipulation). I cannot figure out any handy algorithm for that. For instance, this:

// 0xD000000000000000 = 1101000000000000000000000000000000000000000000000000000000000000

1 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

after rotation becomes this:

// 0x101000100000000 = 0000000100000001000000000000000100000000000000000000000000000000

0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

I wonder if there's any solutions without need to use any pre-calculated hash-table(s)?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（9）

安人多梦 2024-08-16 18:12:21
v = (v & 0x000000000f0f0f0fUL) << 004 | (v & 0x00000000f0f0f0f0UL) << 040 |
    (v & 0xf0f0f0f000000000UL) >> 004 | (v & 0x0f0f0f0f00000000UL) >> 040;
v = (v & 0x0000333300003333UL) << 002 | (v & 0x0000cccc0000ccccUL) << 020 | 
    (v & 0xcccc0000cccc0000UL) >> 002 | (v & 0x3333000033330000UL) >> 020;
v = (v & 0x0055005500550055UL) << 001 | (v & 0x00aa00aa00aa00aaUL) << 010 | 
    (v & 0xaa00aa00aa00aa00UL) >> 001 | (v & 0x5500550055005500UL) >> 010;

v = (v & 0x000000000f0f0f0fUL) << 004 | (v & 0x00000000f0f0f0f0UL) << 040 |
    (v & 0xf0f0f0f000000000UL) >> 004 | (v & 0x0f0f0f0f00000000UL) >> 040;
v = (v & 0x0000333300003333UL) << 002 | (v & 0x0000cccc0000ccccUL) << 020 | 
    (v & 0xcccc0000cccc0000UL) >> 002 | (v & 0x3333000033330000UL) >> 020;
v = (v & 0x0055005500550055UL) << 001 | (v & 0x00aa00aa00aa00aaUL) << 010 | 
    (v & 0xaa00aa00aa00aa00UL) >> 001 | (v & 0x5500550055005500UL) >> 010;
回复 原文
夏日落 2024-08-16 18:12:21

在不使用任何查找表的情况下，我看不出比单独处理每个位更好的了：

unsigned long r = 0;
for (int i = 0; i < 64; ++i) {
    r += ((x >> i) & 1) << (((i % 8) * 8) + (7 - i / 8));
}

Without using any look-up tables, I can't see much better than treating each bit individually:

unsigned long r = 0;
for (int i = 0; i < 64; ++i) {
    r += ((x >> i) & 1) << (((i % 8) * 8) + (7 - i / 8));
}
回复 原文
年少掌心 2024-08-16 18:12:21

有一种有效的方法来执行位反转，即使用 O(log n) 移位操作。如果将 64 位 UINT 解释为 8x8 位数组，则位反转对应于旋转 180 度。

这些转变中有一半有效地执行水平反射；另一半执行垂直反射。为了获得 90 度和 270 度的旋转，可以将正交（即垂直或水平）反射与对角反射结合起来，但后者仍然有点尴尬。

typedef unsigned long long uint64;

uint64 reflect_vert (uint64 value)
{
    value = ((value & 0xFFFFFFFF00000000ull) >> 32) | ((value & 0x00000000FFFFFFFFull) << 32);
    value = ((value & 0xFFFF0000FFFF0000ull) >> 16) | ((value & 0x0000FFFF0000FFFFull) << 16);
    value = ((value & 0xFF00FF00FF00FF00ull) >>  8) | ((value & 0x00FF00FF00FF00FFull) <<  8);
    return value;
}

uint64 reflect_horiz (uint64 value)
{
    value = ((value & 0xF0F0F0F0F0F0F0F0ull) >> 4) | ((value & 0x0F0F0F0F0F0F0F0Full) << 4);
    value = ((value & 0xCCCCCCCCCCCCCCCCull) >> 2) | ((value & 0x3333333333333333ull) << 2);
    value = ((value & 0xAAAAAAAAAAAAAAAAull) >> 1) | ((value & 0x5555555555555555ull) << 1);
    return value;
}

uint64 reflect_diag (uint64 value)
{
    uint64 new_value = value & 0x8040201008040201ull; // stationary bits
    new_value |= (value & 0x0100000000000000ull) >> 49;
    new_value |= (value & 0x0201000000000000ull) >> 42;
    new_value |= (value & 0x0402010000000000ull) >> 35;
    new_value |= (value & 0x0804020100000000ull) >> 28;
    new_value |= (value & 0x1008040201000000ull) >> 21;
    new_value |= (value & 0x2010080402010000ull) >> 14;
    new_value |= (value & 0x4020100804020100ull) >>  7;
    new_value |= (value & 0x0080402010080402ull) <<  7;
    new_value |= (value & 0x0000804020100804ull) << 14;
    new_value |= (value & 0x0000008040201008ull) << 21;
    new_value |= (value & 0x0000000080402010ull) << 28;
    new_value |= (value & 0x0000000000804020ull) << 35;
    new_value |= (value & 0x0000000000008040ull) << 42;
    new_value |= (value & 0x0000000000000080ull) << 49;
    return new_value;
}

uint64 rotate_90 (uint64 value)
{
    return reflect_diag (reflect_vert (value));
}

uint64 rotate_180 (uint64 value)
{
    return reflect_horiz (reflect_vert (value));
}

uint64 rotate_270 (uint64 value)
{
    return reflect_diag (reflect_horiz (value));
}

在上面的代码中，reflect_diag()函数仍然需要很多次转换。我怀疑可以用更少的班次来实现这个功能，但我还没有找到一种方法来做到这一点。

There is an efficient way to perform bit reversal, using O(log n) shift operations. If you interpret a 64-bit UINT as an 8x8 array of bits, then bit reversal corresponds to a rotation by 180 degrees.

Half of these shifts effectively perform a horizontal reflection; the other half perform a vertical reflection. To obtain rotations by 90 and 270 degrees, an orthogonal (i.e. vertical or horizontal) reflection could be combined with a diagonal reflection, but the latter remains an awkward bit.

typedef unsigned long long uint64;

uint64 reflect_vert (uint64 value)
{
    value = ((value & 0xFFFFFFFF00000000ull) >> 32) | ((value & 0x00000000FFFFFFFFull) << 32);
    value = ((value & 0xFFFF0000FFFF0000ull) >> 16) | ((value & 0x0000FFFF0000FFFFull) << 16);
    value = ((value & 0xFF00FF00FF00FF00ull) >>  8) | ((value & 0x00FF00FF00FF00FFull) <<  8);
    return value;
}

uint64 reflect_horiz (uint64 value)
{
    value = ((value & 0xF0F0F0F0F0F0F0F0ull) >> 4) | ((value & 0x0F0F0F0F0F0F0F0Full) << 4);
    value = ((value & 0xCCCCCCCCCCCCCCCCull) >> 2) | ((value & 0x3333333333333333ull) << 2);
    value = ((value & 0xAAAAAAAAAAAAAAAAull) >> 1) | ((value & 0x5555555555555555ull) << 1);
    return value;
}

uint64 reflect_diag (uint64 value)
{
    uint64 new_value = value & 0x8040201008040201ull; // stationary bits
    new_value |= (value & 0x0100000000000000ull) >> 49;
    new_value |= (value & 0x0201000000000000ull) >> 42;
    new_value |= (value & 0x0402010000000000ull) >> 35;
    new_value |= (value & 0x0804020100000000ull) >> 28;
    new_value |= (value & 0x1008040201000000ull) >> 21;
    new_value |= (value & 0x2010080402010000ull) >> 14;
    new_value |= (value & 0x4020100804020100ull) >>  7;
    new_value |= (value & 0x0080402010080402ull) <<  7;
    new_value |= (value & 0x0000804020100804ull) << 14;
    new_value |= (value & 0x0000008040201008ull) << 21;
    new_value |= (value & 0x0000000080402010ull) << 28;
    new_value |= (value & 0x0000000000804020ull) << 35;
    new_value |= (value & 0x0000000000008040ull) << 42;
    new_value |= (value & 0x0000000000000080ull) << 49;
    return new_value;
}

uint64 rotate_90 (uint64 value)
{
    return reflect_diag (reflect_vert (value));
}

uint64 rotate_180 (uint64 value)
{
    return reflect_horiz (reflect_vert (value));
}

uint64 rotate_270 (uint64 value)
{
    return reflect_diag (reflect_horiz (value));
}

In the above code, the reflect_diag() function still requires many shifts. I suspect that it is possible to implement this function with fewer shifts, but I have not yet found a way to do that.

回复 原文
天赋异禀 2024-08-16 18:12:21

如果你想快速做到这一点，你不应该反对查找表。

我会将 64 位整数分解为 N 位块，并在位置选择的转置值表中查找 N 位块。如果选择N=1，则需要在两个槽的表中查找64次，速度相对较慢。如果您选择 N=64，则需要一张表和一次查找，但表很大:-}

N=8 似乎是一个很好的折衷方案。您需要 8 个包含 256 个条目的表。代码应如下所示：

// value to transpose is in v, a long
long r; // result
r != byte0transpose[(v>>56)&0xFF];
r != byte1transpose[(v>>48)&0xFF];
r != byte2transpose[(v>>40)&0xFF];
r != byte3transpose[(v>>32)&0xFF];
r != byte4transpose[(v>>24)&0xFF];
r != byte5transpose[(v>>16)&0xFF];
r != byte6transpose[(v>>08)&0xFF];
r != byte7transpose[(v>>00)&0xFF];

每个表都包含预先计算的值，这些值将输入中的连续位“分散”到 64 位转置结果中。理想情况下，您可以离线计算该值并
只需初始化表条目即可。

如果你不关心速度，那么标准数组转置
算法会起作用；只需索引 64 位，就好像它是位数组一样。

我有一种偷偷的怀疑，人们可能能够使用以下方法来计算转置
有点摆弄类型的黑客。

If you're going to do this fast, you shouldn't object to lookup tables.

I'd break the 64 bit integers into N-bit chunks, and look up the N bit chunks in a position-selected table of transpose values. If you choose N=1, you need 64 lookups in tables of two slots, which is relatively slow. If you choose N=64, you need one table and one lookup but the table is huge :-}

N=8 seems like a good compromise. You'd need 8 tables of 256 entries. The code should look something like this:

// value to transpose is in v, a long
long r; // result
r != byte0transpose[(v>>56)&0xFF];
r != byte1transpose[(v>>48)&0xFF];
r != byte2transpose[(v>>40)&0xFF];
r != byte3transpose[(v>>32)&0xFF];
r != byte4transpose[(v>>24)&0xFF];
r != byte5transpose[(v>>16)&0xFF];
r != byte6transpose[(v>>08)&0xFF];
r != byte7transpose[(v>>00)&0xFF];

Each table contains precomputed values that "spread" the contiguous bits in the input across the 64 bit transposed result. Ideally you'd compute this value offline and
simply initialize the table entries.

If you don't care about speed, then the standard array transpose
algorithms will work; just index the 64 bit as if it were a bit array.

I have a sneaking suspicion that one might be able to compute the transposition using
bit twiddling type hacks.

回复 原文
北城半夏 2024-08-16 18:12:21

为了扩展我对 Ira 答案的评论，您可以使用：

#define ROT_BIT_0(X)    X, (X)|0x1UL
#define ROT_BIT_1(X)    ROT_BIT_0(X), ROT_BIT_0((X) | 0x100UL)
#define ROT_BIT_2(X)    ROT_BIT_1(X), ROT_BIT_1((X) | 0x10000UL)
#define ROT_BIT_3(X)    ROT_BIT_2(X), ROT_BIT_2((X) | 0x1000000UL)
#define ROT_BIT_4(X)    ROT_BIT_3(X), ROT_BIT_3((X) | 0x100000000UL)
#define ROT_BIT_5(X)    ROT_BIT_4(X), ROT_BIT_4((X) | 0x10000000000UL)
#define ROT_BIT_6(X)    ROT_BIT_5(X), ROT_BIT_5((X) | 0x1000000000000UL)
#define ROT_BIT_7(X)    ROT_BIT_6(X), ROT_BIT_6((X) | 0x100000000000000UL)

static unsigned long rot90[256] = { ROT_BIT_7(0) };

unsigned long rotate90(unsigned long v)
{
    unsigned long r = 0;
    r |= rot90[(v>>56) & 0xff];
    r |= rot90[(v>>48) & 0xff] << 1;
    r |= rot90[(v>>40) & 0xff] << 2;
    r |= rot90[(v>>32) & 0xff] << 3;
    r |= rot90[(v>>24) & 0xff] << 4;
    r |= rot90[(v>>16) & 0xff] << 5;
    r |= rot90[(v>>8) & 0xff] << 6;
    r |= rot90[v & 0xff] << 7;
    return r;
}

当然，这取决于 'unsigned long' 是 64 位，并且旋转假设
这些位按行优先顺序排列，最高有效位位于右上角，这似乎是这个问题的情况......

To expand on my comment to Ira's answer, you can use:

#define ROT_BIT_0(X)    X, (X)|0x1UL
#define ROT_BIT_1(X)    ROT_BIT_0(X), ROT_BIT_0((X) | 0x100UL)
#define ROT_BIT_2(X)    ROT_BIT_1(X), ROT_BIT_1((X) | 0x10000UL)
#define ROT_BIT_3(X)    ROT_BIT_2(X), ROT_BIT_2((X) | 0x1000000UL)
#define ROT_BIT_4(X)    ROT_BIT_3(X), ROT_BIT_3((X) | 0x100000000UL)
#define ROT_BIT_5(X)    ROT_BIT_4(X), ROT_BIT_4((X) | 0x10000000000UL)
#define ROT_BIT_6(X)    ROT_BIT_5(X), ROT_BIT_5((X) | 0x1000000000000UL)
#define ROT_BIT_7(X)    ROT_BIT_6(X), ROT_BIT_6((X) | 0x100000000000000UL)

static unsigned long rot90[256] = { ROT_BIT_7(0) };

unsigned long rotate90(unsigned long v)
{
    unsigned long r = 0;
    r |= rot90[(v>>56) & 0xff];
    r |= rot90[(v>>48) & 0xff] << 1;
    r |= rot90[(v>>40) & 0xff] << 2;
    r |= rot90[(v>>32) & 0xff] << 3;
    r |= rot90[(v>>24) & 0xff] << 4;
    r |= rot90[(v>>16) & 0xff] << 5;
    r |= rot90[(v>>8) & 0xff] << 6;
    r |= rot90[v & 0xff] << 7;
    return r;
}

This depends on 'unsigned long' being 64 bits, of course, and does the rotate assuming
the bits are in row-major order with the msb being the upper right, which seems to be the case in this question....

回复 原文
把梦留给海 2024-08-16 18:12:21

使用 IA32 SIMD 这非常容易，有一个方便的操作码可以从 64 位值中提取每八位（这是使用 DevStudio 2005 编写的）：

char
  source [8] = {0, 0, 0, 0, 0, 0, 0, 0xd0},
  dest [8];

__asm
{
  mov ch,3
  movq xmm0,qword ptr [source]
Rotate2:
  lea edi,dest
  mov cl,8
Rotate1:
  pmovmskb eax,xmm0
  psllq xmm0,1
  stosb
  dec cl
  jnz Rotate1
  movq xmm0,qword ptr [dest]
  dec ch
  jnz Rotate2
}

它将数据旋转三次（-270 度），因为 +90 有点棘手（需要多思考一下）

This is quite easy using IA32 SIMD, there's a handy opcode to extract every eighth bit from a 64 bit value (this was written using DevStudio 2005):

char
  source [8] = {0, 0, 0, 0, 0, 0, 0, 0xd0},
  dest [8];

__asm
{
  mov ch,3
  movq xmm0,qword ptr [source]
Rotate2:
  lea edi,dest
  mov cl,8
Rotate1:
  pmovmskb eax,xmm0
  psllq xmm0,1
  stosb
  dec cl
  jnz Rotate1
  movq xmm0,qword ptr [dest]
  dec ch
  jnz Rotate2
}

It rotates the data three times (-270 degrees) since +90 is a bit trickier (needs a bit more thought)

回复 原文
懒的傷心 2024-08-16 18:12:21

如果你把它看作一个二维数组，那么你有解决方案吗？
只需将行设为新列即可。
第一行是最后一列，第二行是最后一列，依此类推。

至少在视觉上，它看起来像您的解决方案。

If you look at this as a 2 dimensional array then you have the solution no?
Just make the rows the new columns.
First row is the last column, 2nd is the one before last and so on.

Visually at least, it looks like your solution.

回复 原文
并安 2024-08-16 18:12:21

可能是这样的

for(int i = 0; i < 8; i++)
{
    for(int j = 0; j < 8; j++)
    {
        new_image[j*8+8-i] = image[i*8+j];
    }
}

probably something like that

for(int i = 0; i < 8; i++)
{
    for(int j = 0; j < 8; j++)
    {
        new_image[j*8+8-i] = image[i*8+j];
    }
}
回复 原文
酒与心事 2024-08-16 18:12:21

如果 if-powered 循环是可以接受的，那么位的公式就足够简单了：

8>>Column - Row - 1

Column 和 Row 都是 0 索引的。

这给你这个映射：

 7 15 23 31 39 47 55 63
 6 14 22 ...
 5 ...
 4 ...
 3 ...
 2 ...
 1 ...
 0  8 16 24 32 40 48 54

If an if-powered loop is acceptable, the formula for bits is simple enough:

8>>Column - Row - 1

Column and Row are 0-indexed.

This gives you this mapping:

 7 15 23 31 39 47 55 63
 6 14 22 ...
 5 ...
 4 ...
 3 ...
 2 ...
 1 ...
 0  8 16 24 32 40 48 54
回复 原文
~没有更多了~

关于作者

花期渐远

暂无简介

0 文章
0 评论
23 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

淡笑忘祈一世凡恋

文章 0 评论 0

我们的影子

文章 0 评论 0

素年丶

文章 0 评论 0

南笙

文章 0 评论 0

18215568913

文章 0 评论 0

qq_xk7Ean

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文