Как проверить, является ли число степенью 2
var s = "1";replaced word
var a = "HRA"; //have to replace
var str = document.getElementById("test").innerHTML;
var count = str.split(a).length - 1;
for (var i = 0; i < count; i++) {
var s = "1";
var a = "HRA";
var str = document.getElementById("test").innerHTML;
var res = str.replace(a, s);
document.getElementById("test").innerHTML = res;
}
<input " type="button" id="Btn_Validate" value="Validate" class="btn btn-info" />
<div class="textarea" id="test" contenteditable="true">HRABHRA</div>10 ответов
Существует простой прием для этой проблемы:
bool IsPowerOfTwo(ulong x)
{
return (x & (x - 1)) == 0;
}
Примечание, эта функция сообщит true для [1 112], который не является питанием [1 113]. Если Вы хотите исключить это, вот то, как:
bool IsPowerOfTwo(ulong x)
{
return (x != 0) && ((x & (x - 1)) == 0);
}
Объяснение
Прежде всего поразрядный двоичный файл & оператор из определения MSDN:
Двоичный файл & операторы предопределены для целочисленных типов и bool. Для целочисленных типов, & вычисляет логическое поразрядное И его операндов. Для bool операндов, & вычисляет логическое И его операндов; то есть, результат верен, если и только если оба его операнда верны.
Теперь позволяют нам смотреть на то, как это все теряет значение:
функция возвращает булевскую переменную (верный / ложь) и принимает один входящий параметр типа, неподписанного длинный (x, в этом случае). Давайте ради простоты предположим, что кто-то передал значение 4 и вызвал функцию как так:
bool b = IsPowerOfTwo(4)
Теперь мы заменяем каждое возникновение x с 4:
return (4 != 0) && ((4 & (4-1)) == 0);
Хорошо мы уже знаем это 4! = 0 evals к истинному, пока неплохо. Но что относительно:
((4 & (4-1)) == 0)
Это переводит в это, конечно:
((4 & 3) == 0)
, Но что точно 4&3?
двоичное представление 4 равняется 100, и двоичное представление 3 равняется 011 (помните & берет двоичное представление этих чисел). Таким образом, мы имеем:
100 = 4
011 = 3
Воображают эти значения сложенными во многом как элементарное дополнение. & оператор говорит, что, если оба значения равны 1 тогда, результат равняется 1, иначе это 0. Так 1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0, и 0 & 1 = 0. Таким образом, мы делаем математику:
100
011
----
000
результат просто 0. Таким образом, мы возвращаемся и смотрим на то, во что теперь переводит наш оператор возврата:
return (4 != 0) && ((4 & 3) == 0);
, Который переводит теперь в:
return true && (0 == 0);
return true && true;
Все мы знаем, что true && true просто true, и это показывает, что для нашего примера, 4 питание 2.
int isPowerOfTwo(unsigned int x)
{
return ((x != 0) && ((x & (~x + 1)) == x));
}
Это действительно быстро. Проверка всех 2 ^ 32 целых чисел занимает около 6 минут и 43 секунды.
Недавно я написал статью об этом на http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in- с / . Он охватывает подсчет битов, правильное использование логарифмов, классическую проверку «x & amp;! (X & amp; (x - 1))» и другие.
Найдите, является ли данное число степенью 2.
#include <math.h>
int main(void)
{
int n,logval,powval;
printf("Enter a number to find whether it is s power of 2\n");
scanf("%d",&n);
logval=log(n)/log(2);
powval=pow(2,logval);
if(powval==n)
printf("The number is a power of 2");
else
printf("The number is not a power of 2");
getch();
return 0;
}
После регистрации вопроса я думал о следующем решении:
Мы должны проверить, является ли точно одна из двоичных единиц информации той. Таким образом, мы просто смещаемся, число исправляют одну цифру за один раз и возврат true, если это равняется 1. Если в какой-либо точке мы приезжаем нечетным числом ((number & 1) == 1), мы знаем, что результат false. Это доказало (использование сравнительного теста) немного быстрее, чем исходный метод для (больших) истинных значений и намного быстрее для лжи или маленьких значений.
private static bool IsPowerOfTwo(ulong number)
{
while (number != 0)
{
if (number == 1)
return true;
if ((number & 1) == 1)
// number is an odd number and not 1 - so it's not a power of two.
return false;
number = number >> 1;
}
return false;
}
, Конечно, решение Greg намного лучше.
Некоторые сайты, что документ и объясняет это и другие взломы битового жонглирования:
- http://graphics.stanford.edu/~seander/bithacks.html
( http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2 ) - http://bits.stephan-brumme.com/
( http://bits.stephan-brumme.com/isPowerOfTwo.html )
И дедушка их, книга "Восхищение Хакера" Henry Warren Jr. :
Как , который объясняет страница Sean Anderson, выражение ((x & (x - 1)) == 0) неправильно указывает, что 0 питание 2. Он предлагает использовать:
(!(x & (x - 1)) && x)
для исправления той проблемы.
private static bool IsPowerOfTwo(ulong x)
{
var l = Math.Log(x, 2);
return (l == Math.Floor(l));
}
bool IsPowerOfTwo(ulong x)
{
return x > 0 && (x & (x - 1)) == 0;
}
Вот простое решение C ++ :
bool IsPowerOfTwo( unsigned int i )
{
return std::bitset<32>(i).count() == 1;
}
cmd + tи типFormBuilder. Помните, что платформа является частью Вашего приложения, просто потому что Вы can' t непосредственно изменяют исходный код doesn' t означают, что Вы не должны быть знакомы с кодом там. – Bastian Hofmann 5 September 2013 в 17:44