Построение Хэша

← →
Вова (2013-03-31 21:35) [0]

5. Постройте хэш. Переведите 64 отдельных бита в одно 64-битное значение. Порядок не имеет значения, если он сохраняется постоянным (я записываю биты слева направо, сверху вниз).

= = 8f373714acfcf4d0

Нашел умную статью, дошел до этого пункта и Вот все понятно, но я не понял. Есть квадрат 8 на 8 клеток. каждая клетка может иметь значение 1 или 0. как в результате получить число такого вида?

и патом как их после этого сравнивать (подсчитываете количество разных битов (это расстояние Хэмминга)

hash: 2BE2E8E3D3CB0
hash: 48847E5536130C10

у них даж длина разная. Я даж нашел код на С++, но не понял нифига, кто нить может на русский делфи перевести?)

// рассчёт расстояния Хэмминга между двумя хэшами // http://ru.wikipedia.org/wiki/Расстояние_Хэмминга // __int64 calcHammingDistance(__int64 x, __int64 y) { __int64 dist = 0, val = x ^ y; // Count the number of set bits while(val) { ++dist; val &= val - 1; } return dist; } (т.е. как искать между "квадратами" я вроде как понял, а как между такими числами?)

// построим хэш __int64 hash = 0; int i=0; // пробегаемся по всем пикселям изображения for( int y=0; y<bin->height; y++ ) { uchar* ptr = (uchar*) (bin->imageData + y * bin->widthStep); for( int x=0; x<bin->width; x++ ) { // 1 канал if(ptr[x]){ // hash |= 1<<i; // warning C4334: "<<" : result of 32-bit shift implicitly converted to 64 bits (was 64-bit shift intended?) hash |= 1i64<<i; } i++; } }

← →
MBo © (2013-04-01 05:34) [1]

^ = xor
++ = Inc
& = and
Затруднения может вызвать последняя строчка - это сброс младшего единичного бита

← →
KilkennyCat © (2013-04-02 02:24) [2]

> __int64 calcHammingDistance(__int64 x, __int64 y)
> {
> __int64 dist = 0, val = x ^ y;
>
> // Count the number of set bits
> while(val)
> {
> ++dist;
> val &= val - 1;
> }
>
> return dist;
> }

function calcHammingDistance (x, y : longint) : longint; var dist, val : longint; begin dist = 0; val = x xor y; while (val) do begin inc(dist); val := val and (val - 1); end result := dist; end;

все просто, сравни и аналогично остальное...

← →
KilkennyCat © (2013-04-02 02:28) [3]

> это сброс младшего единичного бита

странно, обычно для сброса &= ~...

>KilkennyCat © (02.04.13 02:28) [3]
>обычно для сброса &= ~...
это если уже знаем, какой именно бит сбрасывать, а тут такой принцип:
xxxx1000_100 x xxxx1000_011 x-1 изменения касаются только позиции младшей единицы и правее (где в исходном нули) xxxx1000_000 x and (x-1)

ага, упустил с недосыпу "младшего"

Построение Хэша Найти похожие ветки