У меня есть две функции для преобразования битовой позиции в целое число и обратно в битовую позицию. Старшему разработчику не нравится, что я использую цикл для функции IntegerToBitPosition. Есть ли способ сделать это лучше? Я думаю, что это нормально, но он сказал: «Такой, как вы, может использовать цикл для вычисления чего-либо». Можно установить только один бит, и если установлено более одного бита, можно вернуть первый.
private int IntToBitPosition(int intValue)
{
int bitValue = 1;
if (intValue == bitValue)
{
return 0;
}
for (var bitPosition = 1; bitPosition < 32; i++)
{
bitValue *= 2;
if (bitValue == intValue)
{
return bitPosition;
}
}
return 0;
}
private int BitPositionToInt(int bitPosition)
{
int intValue = 0;
intValue |= 1 << bitPosition;
return intValue;
}
Является ли «битовая позиция» на основе 0 или 1? Что должно произойти, если в качестве аргумента используется значение, отличное от степени двойки?
Я настоятельно рекомендую вам написать модульные тесты для этих функций, прежде чем пытаться реализовать другое решение, чтобы вы могли быть уверены в правильности вашего нового решения и/или убедиться, что вы не вносите никаких критических изменений.
Это, вероятно, больше подходит для нашего дочернего сайта Code Review.
Кроме того, int intValue
- пожалуйста, не используйте системную венгерскую нотацию. В этом не было необходимости с тех пор, как мы перестали использовать нетипизированные языки.
Подсказка: используйте switch
вместо O(1)
сопоставления одного конечного набора целых чисел с другим набором.
@dai Это основано на 1. «Можно установить только один бит, и если установлено более одного бита, можно вернуть первый». Можно вернуть только первый совпадающий бит, решением для более чем одной позиции будет список или массив позиций.
@Dai «переключатель» лучше, чем это «для», было бы намного больше кода? Я имею в виду, что я также мог бы использовать рекурсию, но было бы нехорошо читать.
@ 41686d6564 правильно спасибо
@SchmidtA Рискуя показаться снисходительным, вам нужно многому научиться, если вы не знакомы с тем, как работает switch
. Это то, что будет рассмотрено в течение первой недели любого курса бакалавриата, который охватывает C, Java, C# и даже JavaScript.
Вы можете использовать оператор switch
для мгновенного (как в O(1)
временной сложности) поиска любого предопределенного целочисленного значения — если ваш диапазон составляет 1-32, это просто:
private static int IntToBitPosition( int value )
{
switch( value )
{
case 1 << 0: return 1; // The compiler will change `1 << 0` to a constant value allowing its use in a O(1) switch.
case 1 << 1: return 2;
case 1 << 2: return 3;
case 1 << 3: return 4;
case 1 << 4: return 5;
case 1 << 5: return 6;
// etc
case 1 << 28: return 29;
case 1 << 29: return 30;
case 1 << 30: return 31;
case 1 << 31: return 32;
default : return 0;
}
}
Если вы используете Visual Studio и/или MSBuild (я полагаю, что вы), вы можете избавить себя от необходимости писать случаи переключения вручную, используя T4:
private static int IntToBitPosition( int value )
{
switch( value )
{
<# for( Int32 i = 0; i <= 31; i++ ) { #>
case << <#= ( 1 << i ) #>: return <#= i + 1 #>
<# } #>
default: return 0;
}
}
Конечно, более проницательные читатели будут знать, что ваша функция IntToBitPosition
на самом деле просто выполняет Log2(n) + 1
, которую можно мгновенно вычислить для любого целого числа , используя этот подход :
public static int Log2(int v)
{
int r = 0xFFFF - v >> 31 & 0x10;
v >>= r;
int shift = 0xFF - v >> 31 & 0x8;
v >>= shift;
r |= shift;
shift = 0xF - v >> 31 & 0x4;
v >>= shift;
r |= shift;
shift = 0x3 - v >> 31 & 0x2;
v >>= shift;
r |= shift;
r |= (v >> 1);
return r;
}
Мне не нравится решение с переключателем, потому что я не думаю, что оно лучше. Но второй есть.
@SchmidtA Что делает что-то «лучше» для вас? Если это производительность, switch
нельзя превзойти.
Помните, что такое бинарность, сила двоек. Чтобы преобразовать бит в целое, это просто 2 в степени битовой позиции.
Таким образом, BitPositionToInt равен 2^bitPosition.
Итак, 2^4 = 16.
Противоположностью этому является получение журнала значения с основанием 2. В С# вы можете использовать функцию Math.Log
например если значение равно 16
Math.Log(16, 2)
Что возвращает 4.
Обратите внимание, что это не вернет «первую» битовую позицию, если int не является значением в степени 2. Если вы хотите сделать это, вам все еще нужен цикл, но вы, безусловно, можете его упростить.
private int IntToBitPosition(int value){
int position=0;
while((value & 1)==0 && value>0){
position++;
value= value >> 1;
}
return position;
}
Итак, что мы делаем здесь, это объединяем значение И с 1, чтобы увидеть, установлен ли бит 0. Если это не так, сдвиньте значение вправо (которое делит его на 2) и проверяйте снова, пока бит не будет установлен или значение не станет равным 0.
(обратите внимание, я не проверял приведенную выше процедуру, но вы должны понять).
Да, с этим предположением, это было бы лучшим решением. Я думаю, это то, что он имел в виду, даже если бы он мог быть более дружелюбным. Отмечу как правильный ответ.
Если вы ориентируетесь на .NET Core 3.0 или .NET 5, вы можете использовать BitOperations.Log2(int).
private int IntToBitPosition(int intValue)
{
return System.Numerics.BitOperations.Log2(intValue);
}
Ваш «Старший разработчик» должен поддерживать, обучать и поощрять своих подчиненных. Похоже, он оскорбляет вас. надеюсь ошибаюсь...