Я готовлюсь к интервью, используя текст "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", сдвинутому влево я + 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
Итак, & с этой маской очищает самый старший бит до 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
Итак, & с этими масками очищает биты до индекса i
Первая функция:
Возьмем, например, i=3. (1 << i) будет давать 1000 в двоичном формате. Вычитая 1 из того, что дает вам 0111 в двоичном (это число 1). ANDing, что с номером будет очищаться все, кроме последних бит i, как описано в описании функции.
Вторая функция:
Для второй функции применяется то же самое. Если i=3, то ((i << (i+1)) - 1) дает нам 01111. Тильда инвертирует биты, поэтому мы имеем 10000. Это важно сделать так, вместо того чтобы просто сдвинуть оставшиеся биты i, потому что перед нашей маской может быть любое количество значимых бит (так что 10000 может быть длиной 8 бит и выглядеть как 11110000. тильда получает нас, просто чтобы быть ясным). Затем число AND с маской для окончательного результата
//Чтобы очистить все биты от самого значащего бита через я (включительно), мы делаем:
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)-1 will clear the bits from msb to i
//Чтобы очистить все биты от я до 0 (включительно), сделаем следующее:
int clearBitsIthrough0(int num, int i) {
int mask = ~(((1 << (i+1)) - 1);
return num & mask;
}
тот же пример я = 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