Я готовлюсь к собеседованию, используя текст «Cracking the Coding Interview» от Gayle Laakman McDowell. В разделе, посвященном манипуляции бит, есть две функции, которые предоставляются, но я не совсем понимаю, как это работает.
// To clear all bits from the most significant bit through i (inclusive), we do: int clearMSBthroughI(int num, int i) { int mask = (1 << i) - 1; return num & mask; } // To clear all bits from i through 0 (inclusive), we do: int clearBitsIthrough0(int num, int i) { int mask = ~(((1 << (i+1)) - 1); return num & mask; } В первой функции я понимаю, что (1 << i) , конечно, но то, что я не уверен, заключается в том, как вычитание 1 из этого значения влияет на биты (т. Е. (1 << i) - 1) ).
У меня в основном такая же путаница со второй функцией. Для каких эффектов, в частности, для битов, вычитает ли 1 из ((1 << (i+1)) ? По моему мнению, ((1 << (i+1)) приводит к единому бит «on», сдвинуто налево i + 1 раз – что вычитает это на 1?
Спасибо, и я надеюсь, что это было ясно! Пожалуйста, дайте мне знать, если есть другие вопросы.
Для тех, кто случайно имеет текст, на который я ссылаюсь, он находится на странице 91 в 5-м выпуске.
предположим, что i= 5
(1 << i) дает вам 0100000 1 помещается в позицию 6-го бита
так что теперь, если мы выставим 1 из него, тогда получим 0011111 ==> только 5 первых бит установлены в 1 а другие установлены в 0 и именно так мы получаем нашу маску
Вывод: для дачи i (1 << i) -1 даст вам маску с первым битом i установленным в 1 а другие - 0
По первому вопросу:
скажем, i = 5
(1 << i ) = 0010 0000 = 32 in base 10 (1 << i ) -1 = 0001 1111 = 31
Таким образом, a & с этой маской очищает самый старший бит до i, потому что все позиции битов выше и включая индекс i будут равны 0, и каждый ниже будет 1.
По второму вопросу:
Опять скажем, i = 5
(1 << (i + 1)) = 0100 0000 = 64 in base 10 (1 << (i + 1)) - 1 = 0011 1111 = 63 ~((1 << (i + 1)) - 1) = 1100 0000 = 192
Таким образом, a & с этими масками очищает биты до индекса i
Первая функция:
Возьмем, например, i=3 . (1 << i) даст 1000 в двоичном формате. Вычитая 1 из того, что дает вам 0111 в двоичном (это число из 1). ANDing, что с номером будет очищаться все, кроме последних бит i, как описано в описании функции.
Вторая функция:
Для второй функции применяется то же самое. Если i=3 , то ((i << (i+1)) - 1) дает 01111 . Тильда инвертирует бит, поэтому у нас есть 10000 . Это важно сделать так, вместо того, чтобы просто переместить i биты влево, потому что может быть любое количество значительных бит перед нашей маской (так что 10000 может быть длиной 8 бит и выглядеть как 11110000 Это то, что нас достала тильда, быть ясным). Затем число AND с маской для окончательного результата
// Чтобы очистить все биты от самого значащего бита через i (включительно), мы делаем:
int clearMSBthroughI(int num, int i) { int mask = (1 << i) - 1; return num & mask; } Take the example of i = 3 1<<3 gives you 0x00001000 (1<<3)-1 gives you 0x00000111 num & (1<
// Чтобы очистить все биты от i до 0 (включительно), мы делаем:
int clearBitsIthrough0(int num, int i) { int mask = ~(((1 << (i+1)) - 1); return num & mask; }
тот же пример i = 3 дает вам
1 <<(3+1) =0x00010000 1 <<(3+1)-1 = 0x00001111 mask =~(1<<(3+1)-1) = 0x11110000 num & mask will cleaR the bits from 0 throuh i