Лучшая логика для этого побитового выражения?

Я работаю над программой, которая работает с файлом, использующим хэши. Данные разбиты на блоки длиной 0x1000. Мне нужно рассчитать количество блоков, покрываемых сегментом с определенным начальным и конечным смещением.

Например, если начальное смещение сегмента было 0x2000, а конечное — 0x3523, это означало бы, что он занимает два блока: 0x2000 и 0x3000. Он не занимает все 0x2000 байт в блоках данных, но считается, что он «занимает блок», когда он находится внутри него. Первой мыслью было сделать:

( ( EndingOffset - StartingOffset ) + 0xFFF ) >> 0xC

Это эквивалент Math.Ceil((EndingOffset - StartingOffset) / 0x1000), но я новичок в побитовых операторах, и мне нравится работать с ними.

В любом случае, логика была ошибочной, и именно в этом случае я понял, что если начальное смещение равно 0x3D8A, а конечное смещение 0x671D, разница между ними составляет 0x2993. Округлив это 0x3000, или три блока. Сегмент фактически занимает четыре: 0x3000, 0x4000, 0x5000 и 0x6000. Итак, мой следующий поезд, и, к сожалению, мой последний, состоял в том, чтобы вместо этого найти разницу между смещением первого блока, в котором находится сегмент, и смещением первого блока, в котором сегмента нет.

С 0x3D8A и 0x671D это приводит меня к (0x7000 - 0x3000) >> 0xC, что успешно дает правильное количество блоков, 4. Я хочу улучшить то, как я это написал, а именно:

BlockSize = ((((OffsetEnd + 0xFFF) >> 12) + 1) - ((OffsetStart + 0xFFF) >> 12));

Я знаю, что слишком усложнил простую задачу, но я не могу сообразить, как написать ее лучше.

редактировать: Это неловко. Я не знаю, как я пришел к этому вместо

(((OffsetEnd + 0xFFF) >> 12) - (OffsetStart >> 12));

Хотя все еще не кажется полным.

редактировать 2: Извините, забыл упомянуть, что конечное смещение является исключительным, а не включающим и является позицией после последнего байта сегмента, означающего:

(((OffsetEnd - 1 + 0xFFF) >> 12) - (OffsetStart >> 12));

edit 3: Отходя от ответа Керека, я получаю:

BlockSize = 1 + (offsetEnd - 1 >> 12) - (offsetStart >> 12);

..или, считая от 0,

BlockSize = (offsetEnd - 1 >> 12) - (offsetStart >> 12);

редактировать 4: Забудьте о счете с нуля, я придерживаюсь:

BlockSize = 1 + (offsetEnd - 1 >> 12) - (offsetStart >> 12);

c++ c# logic bit-manipulation bitwise-operators
person mowwwalker    schedule 04.01.2012    source источник
comment
Является ли конечное смещение инклюзивным или исключительным?   -  person Kerrek SB    schedule 04.01.2012
comment
Эксклюзив. Извините, надо было уточнить   -  person mowwwalker    schedule 04.01.2012

Ответы (2)


arrow_upward
0
arrow_downward

Предположим, что ваши диапазоны данных представлены в виде [start, end), это очень просто:

unsigned int start_block = start_offset / 0x1000;
unsigned int end_block = end_offset / 0x1000;

unsigned int number_of_blocks = end_block - start_block + (end_offset > start_offset && end_offset % 0x1000 > 0 ? 1 : 0);

Я полагаю, эквивалентом / 0x1000 является >> 12.

Ваши данные будут занимать диапазон блоков [start_block, end_block). Обратите внимание, что блок 0 — это [0x0000, 0x1000), блок 1 — это [0x1000, 0x2000)` и т. д.

Как указал @Ron, вам понадобится одно условное выражение, чтобы отличить, является ли последний («однопрошлый») блок пустым или нет, и увеличить количество блоков на единицу в последнем случае.

person Kerrek SB    schedule 04.01.2012
comment
Это была моя первоначальная логика, но 0x3D8A станет 3, 0x671D станет 6, а число станет 3, хотя должно быть 4. - person mowwwalker; 04.01.2012
comment
@Walkerneo: Нет, это должно быть 3, так как нумерация начинается с нуля! - person Kerrek SB; 04.01.2012
comment
Ничего себе, ты прав. Не знаю, почему это не пришло мне в голову. - person mowwwalker; 04.01.2012
comment
Я бы изменил это, добавив единицу к number_of_blocks, так как количество блоков не должно основываться на нуле (в отличие от последнего блока index, который должен). - person Ron Warholic; 04.01.2012
comment
@Walkerneo: проверьте связанную статью. Возможно, у вас есть веские аргументы, почему Дейкстра ошибся, но, как видите, счет с отсчетом от нуля делает все довольно просто. - person Kerrek SB; 04.01.2012
comment
@Ron: Если у меня нет данных, я использую нулевые блоки, не так ли? - person Kerrek SB; 04.01.2012
comment
@KerrekSB, когда-нибудь было легко переключаться между программным подсчетом и подсчетом реальных слов? Я продолжаю сталкиваться с этой проблемой. - person mowwwalker; 04.01.2012
comment
@Walkerneo: прочитайте статью по ссылке. Дийкстра — довольно умный человек, и к нему стоит прислушаться. Он говорит, как лучше думать о счете с отсчетом от нуля, чтобы он казался естественным. - person Kerrek SB; 04.01.2012
comment
@KerrekSB: Да, однако, если вы используете один блок, вам все равно нужно различать один и нулевой блоки, возвращаемые в любом случае. Например, если у вас есть 0x3000 и 0x3FFF в качестве начала и конца, вы получите number_of_blocks = 0. Как вы отличите это от отсутствия данных без условного выражения? - person Ron Warholic; 04.01.2012
comment
@KerrekSB, здесь мне придется согласиться с Роном. Прочитал статью и полностью согласен, но там ничего не сказано о подсчете, только индексация. Как мы определяем диапазон и как мы определяем порядковый номер элемента диапазона. Имеет смысл, чтобы элемент 0 был первым, но не столько, чтобы в элементе 0 у нас было 0 элементов, а скорее 1. - person mowwwalker; 04.01.2012
comment
@Walkerneo: Дейкстра предлагает вам думать о 0 как о количестве элементов, которые идут перед вашим элементом. Таким образом, в элементе 0 у нас нет прецедентов элементов. Начинать считать с 1 — это такой же вопрос условности, как и начинать с 0, и, поскольку последнее гораздо более практично для вычислений, стоит проявить некоторую гибкость в своих привычках! :-) - person Kerrek SB; 04.01.2012

arrow_upward
0
arrow_downward

( ( EndingOffset - StartingOffset ) + 0xFFF ) >> 0xC + (StartingOffset & ~(0xFFF) != 0)

Это будет иметь краткое начало, которое у вас есть, и оно увидит, попадает ли StartingOffset на границу блока или нет. Если нет, добавьте 1.

person nmjohn    schedule 04.01.2012