Вращение битового массива 90 градусов
T-SQL (SQL Server 2005) функция, включая тестовые сценарии:
if exists (select 1 from sys.objects where object_id = object_id(N'dbo.fnGetNumberString'))
drop function fnGetNumberString
go
/*
Tests:
declare @tests table ( testValue bigint )
insert into @tests select -43213 union select -5 union select 0 union select 2 union select 15 union select 33 union select 100 union select 456 union select 1024 union select 10343 union select 12345678901234 union select -3434343434343
select testValue, dbo.fnGetNumberString(testValue) as textValue
from @tests
*/
create function dbo.fnGetNumberString
(
@value bigint
)
returns nvarchar(1024)
as
begin
if @value = 0 return 'zero' -- lets me avoid special-casing this later
declare @isNegative bit
set @isNegative = 0
if @value < 0
select @isNegative = 1, @value = @value * -1
declare @groupNames table ( groupOrder int, groupName nvarchar(15) )
insert into @groupNames select 1, '' union select 2, 'thousand' union select 3, 'million' union select 4, 'billion' union select 5, 'trillion' union select 6, 'quadrillion' union select 7, 'quintillion' union select 8, 'sextillion'
declare @digitNames table ( digit tinyint, digitName nvarchar(10) )
insert into @digitNames select 0, '' union select 1, 'one' union select 2, 'two' union select 3, 'three' union select 4, 'four' union select 5, 'five' union select 6, 'six' union select 7, 'seven' union select 8, 'eight' union select 9, 'nine' union select 10, 'ten' union select 11, 'eleven' union select 12, 'twelve' union select 13, 'thirteen' union select 14, 'fourteen' union select 15, 'fifteen' union select 16, 'sixteen' union select 17, 'seventeen' union select 18, 'eighteen' union select 19, 'nineteen'
declare @tensGroups table ( digit tinyint, groupName nvarchar(10) )
insert into @tensGroups select 2, 'twenty' union select 3, 'thirty' union select 4, 'forty' union select 5, 'fifty' union select 6, 'sixty' union select 7, 'seventy' union select 8, 'eighty' union select 9, 'ninety'
declare @groups table ( groupOrder int identity, groupValue int )
declare @convertedValue varchar(50)
while @value > 0
begin
insert into @groups (groupValue) select @value % 1000
set @value = @value / 1000
end
declare @returnValue nvarchar(1024)
set @returnValue = ''
if @isNegative = 1 set @returnValue = 'negative'
select @returnValue = @returnValue +
case when len(h.digitName) > 0 then ' ' + h.digitName + ' hundred' else '' end +
case when len(isnull(t.groupName, '')) > 0 then ' ' + t.groupName + case when len(isnull(o.digitName, '')) > 0 then '-' else '' end + isnull(o.digitName, '') else case when len(isnull(o.digitName, '')) > 0 then ' ' + o.digitName else '' end end +
case when len(n.groupName) > 0 then ' ' + n.groupName else '' end
from @groups g
join @groupNames n on n.groupOrder = g.groupOrder
join @digitNames h on h.digit = (g.groupValue / 100)
left join @tensGroups t on t.digit = ((g.groupValue % 100) / 10)
left join @digitNames o on o.digit = case when (g.groupValue % 100) < 20 then g.groupValue % 100 else g.groupValue % 10 end
order by g.groupOrder desc
return @returnValue
end
go
8 ответов
Без использования справочных таблиц я не вижу ничего лучше, чем рассматривать каждый бит по отдельности:
unsigned long r = 0;
for (int i = 0; i < 64; ++i) {
r += ((x >> i) & 1) << (((i % 8) * 8) + (7 - i / 8));
}
Существует эффективный способ выполнения инверсии битов с использованием операций сдвига 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));
}
В приведенном выше коде для функции reflection_diag () по-прежнему требуется много сдвиги. Я подозреваю, что эту функцию можно реализовать с меньшим количеством смен, но я еще не нашел способа сделать это.
Если вы собираетесь сделать это быстро, вы не должны возражать против таблиц поиска.
Я бы разбил 64-битные целые числа на N-битные блоки и посмотрел бы N-битные блоки в выбранной позиции таблица значений транспонирования. Если вы выберете N = 1, вам потребуется 64 поиска в таблицах из двух слотов, что относительно медленно. Если вы выберете N = 64, вам понадобится одна таблица и один поиск, но таблица огромна: -}
N = 8 кажется хорошим компромиссом. Вы' d нужно 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-битный массив, как если бы это был битовый массив.
У меня есть скрытое подозрение, что можно было бы вычислить транспозицию, используя бит-твидл-хаки.
Чтобы расширить мой комментарий к ответу Иры, вы можете использовать:
#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 бита, и выполняется ли вращение в предположении биты расположены в порядке старших строк, причем старший бит - это верхний правый угол, что, кажется, имеет место в этом вопросе ....
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)
Если вы посмотрите на это как на двумерный массив, то у вас есть решение нет? Просто сделайте строки новыми столбцами. Первая строка - это последний столбец, вторая - предпоследняя и т. Д.
По крайней мере, визуально это похоже на ваше решение.
, вероятно, что-то в этом роде
for(int i = 0; i < 8; i++)
{
for(int j = 0; j < 8; j++)
{
new_image[j*8+8-i] = image[i*8+j];
}
}
Если петля с питанием от сети приемлемо, формула для битов достаточно проста:
8>>Column - Row - 1
Столбец и Строка проиндексированы 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