Эффективный алгоритм C # на основе целых чисел

Question

Я смотрю на Наиболее эффективный способ реализации целочисленной степенной функции pow (int, int) .

Это ответ, который они получили.

Я пытаюсь заставить его работать на C #, но я сравниваю int с bool и всем прочим. , , и я не могу понять, почему они сравнивают & 1, разве это не значит и верно? Какой смысл в этом. Это не кажется эффективным.

 int ipow(int base, int exp) 
 { 
     int result = 1; 
     while (exp) 
     { 
         if (exp & 1) 
             result *= base; 
         exp >>= 1; 
         base *= base; 
     } 

return result; 

}

Я делаю exp == в сравнении, но это 1 все еще там, и я не знаю, нужно ли мне это.

Кто-нибудь знает, для чего нужна 1 в «if (exp & 1)»? Или если мне это нужно? Я не вижу смысла.

Answer 1

В основном в C и C ++ условие if / while - это «если выражение ненулевое».

Так что в этом случае вы захотите:

while (exp != 0)

и

if ((exp & 1) != 0) // If exp is odd

Вы также хотели бы избежать использования ключевого слова base:)

Я не проверял, будет ли алгоритм работать в C #, но это должно как минимум помочьВы делаете еще один шаг вперед.

Answer 2

Вот версия метода на C #:

int ipow(int base, int exp) {
   int result = 1; 
   while (exp > 0) {
      if ((exp & 1) != 0) { 
         result *= base;
      } 
      exp >>= 1; 
      base *= base; 
   } 
   return result; 
}

(Как отметил Джон, вам следует избегать использования base в качестве имени переменной, однако я сохранил его в коде, чтобы сделать его похожим на Coriginal.)

Когда вы используете оператор & для двух целых чисел (exp и 1), это бинарный оператор.Цель состоит в том, чтобы замаскировать наименьший значащий бит в значении exp.

Метод заключается в том, что он проходит через биты в значении exp и умножает базовые значения, умноженные, чтобы соответствовать значениюбиты в значении exp.

Если значение exp, например, равно 21, то это 10101 в двоичном формате со значениями битов 16 + 4 + 1.Вместо умножения базового значения в 21 раз оно умножается на 16 * базовое, 4 * базовое и 1 * базовое.

Answer 3

'&' - бинарный оператор. '&&' - логический оператор. Допустим, у вас есть

int a = 5, b = 1;
int c = a & b;

Ваш 'a' на самом деле 00000101 в двоичном формате, а b - 00000001. Когда вы делаете a & b, это означает, что вы должны выполнить операцию AND для каждого из этих битов. номера. То есть первые биты будут «добавлены», а вторые и так далее. Результат в C будет 00000001. Поскольку единственное место, где AND b равны 1, это последний бит.

Вы можете сделать то же самое с оператором или ('|').

int d = a | b; //d = 00000101

оператор beacause ИЛИ запрашивает, чтобы хотя бы один бит был истинным;

Answer 4

Проблема, с которой вы столкнулись, состоит в том, что C использует числа для получения логических значений. Поэтому сравнение int с 1 выполнит операцию AND над двумя значениями, а затем примет результат и оценит его как логическое значение.

C # не будет делать то же самое, вам нужно переосмыслить алгоритм здесь