Эта серия представляет собой краткое изложение структур данных и алгоритмов, когда я искал работу много лет назад. Здесь есть базовые части и классические вопросы для интервью от крупных компаний. Впервые опубликовано на CSDN. Теперь он организован в серию для справки друзей, которым это нужно.Если есть какая-либо ошибка, пожалуйста, поправьте меня. Полный кодовый адрес этой серии находится по адресуздесь.
0 Обзор
Математика является основой науки, и на собеседованиях часто разыгрываются числовые вопросы. Математика сама по себе интересный предмет.Некоторое время назад я плохо выполнял свою работу, поэтому у меня появился сильный интерес к математике, поэтому я прочитал несколько книг по истории математики, а также купил "Элементы геометрии" и «Настоящий анализ Тао Чжэсюань».Некоторые главы принесли много пользы, и те, кому интересно, могут ознакомиться. В частности, «Начала геометрии», работа Евклида тысячи лет назад, способ мышления и доказательства в ней действительно вдохновляют, подходят для всех возрастов. В этой статье сначала суммируются числовые вопросы в вопросах интервью. Я пытаюсь добавить некоторые математические доказательства. Если есть какие-либо ошибки, пожалуйста, поправьте меня. Код этой статьи находится вздесь.
1 Найдите задачу с простыми числами
вопрос:Напишите программу, которая находит первые N простых чисел. Например, если N равно 100, найдите первые 100 простых чисел.
анализировать:Простое число (или простое число) относится к числу больше 1, которое не может делиться на другие натуральные числа, кроме 1 и самого числа, например2，3，5.... Самая основная идея состоит в том, чтобы оценить каждое число от 1 до N и вывести, является ли оно простым числом. Улучшением было бы отсутствие необходимости оценивать все числа от 1 до N, потому что четные числа, кроме 2, определенно не являются простыми числами, а нечетные числа могут быть простыми, а могут и не быть. Тогда мы можем пропустить числа, кратные 2 и 3, т.е. для6n，6n+1, 6n+2, 6n+3, 6n+4, 6n+5, нам остается только судить6n+1и6n+5Будь то простое число.
Самый простой способ определить, является ли число m простым, — это разделить m на число от 2 до m - 1. Если существует число, на которое можно разделить m, то m не является простым числом. Судить о том, является ли m простым числом, можно еще лучше: нет необходимости делить m на все числа от 2 до m-1, а нужно делить только на числа от 2 до квадратного корня из m. если используется2，3，4，5...根号mРазделить м. На самом деле это все равно пустая трата времени, потому что если 2 не делится, то не делятся и числа, кратные 2. Точно так же, если 3 не делится, то и кратные 3 тоже не делятся, поэтому можно использовать только простые числа от 2 до m, которые меньше корня из m. Просто удалите его.
развязать:Вы можете заранее получить 2, 3, 5 как простые числа, затем пропустить числа, кратные 2 и 3, начать с 7, затем оценить 11, затем оценить 13, затем 17... Правило состоит в том, чтобы прибавить 2 к 5, затем добавьте 4, а затем добавьте 2, затем добавьте 4. Это можно повторить, как показано на рисунке ниже, просто нужно судить7，11，13，17，19，23，25，29...эти числа.
Чтобы судить, является ли это простым числом, используется улучшенная схема, то есть число между 2 и знаком корня m делится на m, чтобы судить. Следует отметить, что вы не можете напрямую использовать корень числа m для суждения, потому что для некоторых чисел, таких как 121, корневое число может быть 10,999999, поэтому лучше всего использовать для суждения умножение, как показано в коде.
/**
* 找出前N个质数, N > 3
*/
int primeGeneration(int n)
{
int *prime = (int *)malloc(sizeof(int) * n);
int gap = 2;
int count = 3;
int maybePrime = 5;
int i, isPrime;
/* 注意：2, 3, 5 是质数 */
prime[0] = 2;
prime[1] = 3;
prime[2] = 5;
while (count < n) {
maybePrime += gap;
gap = 6 - gap;
isPrime = 1;
for (i = 2; prime[i]*prime[i] <= maybePrime && isPrime; i++)
if (maybePrime % prime[i] == 0)
isPrime = 0;
if (isPrime)
prime[count++] = maybePrime;
}
printf("\nFirst %d Prime Numbers are :\n", count);
for (i = 0; i < count; i++) {
if (i % 10 == 0) printf("\n");
printf("%5d", prime[i]);
}
printf("\n");
return 0;
}
2 Проблема с 0 в конце факториала
вопрос:Если задано целое число N, то факториал N равен N! Сколько нулей в конце? (Этот вопрос взят из "Красоты программирования").
Решение 1:Популярное решение состоит в том, что если N! = К10M, а K не делится на 10, то N! В конце M нулей. Считайте Н! Первичная факторизация возможна, N! = (2X) * (3Y) * (5Z)..., то поскольку 10 = 25, поэтому количество нулей такое же, какXиZСвязано, каждая пара 2 и 5 умножается, чтобы получить 10, поэтому количество 0sM = min(X， Z), очевидно, что количество вхождений 2 больше, чем 5, поэтому количество 0 - это количество вхождений 5. Отсюда можно написать следующий код:
/**
* N!末尾0的个数
*/
int numOfZero(int n)
{
int cnt = 0, i, j;
for (i = 1; i <= n; i++) {
j = i;
while (j % 5 == 0) {
cnt++;
j /= 5;
}
}
return cnt;
}
Решение 2:Продолжение анализа может улучшить приведенный выше код, чтобы найти, сколько пятерок в факторизации от 1 до N, пусть Z=N/5 + N/(52) + N/(53)+... То есть N/5 означает, что числа, кратные 5 в числах от 1 до N, вносят 5, N/(52) означает 52Число, кратное 5, дает дополнительные 5.... Чтобы привести простой пример, такой как определение количества пятерок в факторизации числа от 1 до 100, вы можете знать, что существует 20 кратных 5 и 4 кратных 25, поэтому всего 24 пятерки. код показывает, как показано ниже:
/**
* N!末尾0的个数-优化版
*/
int numOfZero2(int n)
{
int cnt = 0;
while (n) {
cnt += n/5;
n /= 5;
}
return cnt;
}
Суммировать:Вышеприведенный анализ блеклый, но следует упомянуть, что он включает в себя фундаментальную теорему арифметики, котораяЛюбое натуральное число больше 1 можно разложить на произведение простых чисел, и метод разложения уникален.Доказательство теоремы разделено на две части: существование и единственность. Доказательство следующее:
доказательство существования
Используйте доказательство от противного, чтобы доказать, что существуют натуральные числа больше 1, которые не могут быть записаны как произведение простых чисел, и назовите наименьшее из них n. Натуральные числа можно разделить на три категории в зависимости от их делимости (могут ли они быть выражены как произведение двух натуральных чисел, которые не являются самими собой): простые числа, составные числа и 1.
- Во-первых, по определению n больше 1.
- Во-вторых, n не является простым числом, потому что простое число p можно записать в виде произведения простых чисел: p=p, что не соответствует предположению. Таким образом, n может быть только составным числом, но каждое составное число можно разложить на произведение двух натуральных чисел, строго меньших его самого и больших 1. Предполагать
n = a*b, a и b оба являются числами больше 1 и меньше n. Это видно из предположения, что и a, и b можно разложить в произведение простых чисел, поэтому n также можно разложить в произведение простых чисел, так что это противоречит предположению. Это доказывает, что все натуральные числа больше 1 можно разложить в произведение простых чисел.
Доказательство уникальности
- Когда n=1, действительно существует только одно разложение.
- Предположим, что для натуральных чисел n>1 существуют две факторизации: n=p1...pm = q1...qk,Испуганный1<=...<=pm, д1<=...<=qk, где p и q — простые числа, мы хотим доказать, что p1=q1,Испуганный2=q2...если не равно, мы можем установить p1 < q1, так что п1меньше, чем все qs. из-за п1и д1являются простыми числами, поэтому их наибольший общий делитель равен 1, а алгоритм Евклида показывает, что существуют целые числа a и b такие, что a * p1 + b * q1= 1. следовательно а*р1 * q2...qk + b * q1 * q2...qk = q2...qk(Уравнение 1). из-за q1...qk= n, поэтому левая часть уравнения 1 равна p1целое число, кратное , так что q в правой части уравнения 12...qkтоже должно быть п1целое число, кратное , поэтому должно быть p1 = qi, я > 1. И это то же самое, что и предыдущий p1меньше всех q противоречит, поэтому по симметрии для p1 > q1Аналогичные выводы можно сделать и в этом случае, поэтому можно доказать, что p1 = q1, таким же образом мы можем получить p2 = q2...pm=qk, что завершает доказательство единственности.
3 Количество единиц в 1-N положительных целых числах
вопрос:Для заданного положительного десятичного числа N найдите количество целых чисел от 1 до N, содержащих 1. Например, при N = 23 количество единиц равно 13. Среди них 1, 11 и 21 в разряде единиц, всего 3 и 10 в разряде десятков, в том числе 10, 11...19, поэтому общее количество единиц равно3 + 10 = 13Кусок.
анализировать:Наиболее естественная идея состоит в том, чтобы перейти от 1 к N напрямую, найти количество единиц, содержащихся в каждом числе, а затем сложить эти числа, чтобы получить общее количество единиц. Ему нужно пройти N чисел, и каждое вычисление числа 1 требует O(log10N), сложность алгоритма O(Nlog10Н). Когда число N велико, алгоритм будет выполняться долго, должен быть лучший способ.
развязать:Мы можем начать анализ с 1 цифры и постепенно находить закономерность.
-
Когда N равно 1 цифре, количество единиц f(N) равно 1 для N>=1.
-
Когда N является двузначным числом, количество единиц в разряде единиц связано не только с разрядом единиц, но и с разрядом десятков.
- Когда N=23, количество единиц в разряде единиц составляет всего 1, 11, 21, а количество единиц в разряде десятков составляет всего 10, 11...19, поэтому количество единиц
f(N) = 3+10 = 13. Если одна цифра N >=1, количество вхождений 1 в одну цифру равно числу десятков плюс 1; если одна цифра N равна 0, количество вхождений 1 в одну цифру равно числу десятков. - Количество вхождений 1 в цифре десятков аналогично. Если цифра десятков N равна 1, количество вхождений 1 в цифре десятков равно количеству каждой цифры плюс 1, если цифра десятков N больше чем 1, в разряде десятков появляется 1. Количество раз равно 10.
- Когда N=23, количество единиц в разряде единиц составляет всего 1, 11, 21, а количество единиц в разряде десятков составляет всего 10, 11...19, поэтому количество единиц
-
Когда N равно 3 цифрам, количество единиц может быть получено с помощью того же анализа. Если N=123, мы можем получить
1出现次数 = 13+20+24 = 57. -
Когда N равно 4,5...K цифр, мы предполагаем
N=abcde, то для вычисления количества единиц в разряде сотен на него влияют три фактора: число в разряде сотен, число ниже разряда сотен и число выше разряда сотен.- Если цифра в разряде сотен равна 0, количество единиц в разряде сотен определяется старшими цифрами. Например, N=12013, есть 100~199, 1000~1199, 2100~2199...11100~111999, и есть 1200 чисел с 1 в разряде сотен, что равно старшему разряду сотен. (12)*текущий номер (100).
- Если число в разряде сотен равно 1, количество вхождений 1 в разряде сотен зависит не только от более высокого разряда, но и от более низкого разряда. Например, 12113, есть 1200 + 114 = 1314 случаев, когда 1 появляется в разряде сотен, то есть 12 * 100 влияет на высокое положение + 113 + 1 влияет на низкое положение = 114.
- Если цифра в разряде сотен другая, количество вхождений 1 в разряде сотен определяется только старшей цифрой. Например, 12213, если 1 в разряде сотен равен (12+1)*100=1300.
Используя приведенные выше идеи анализа, напишите следующий код. где low представляет младшую цифру, curr представляет цифру рассматриваемой в данный момент цифры, а high представляет старшую цифру. Простой анализ, учитывая число 123, сначала рассмотрим одну цифру, затем curr равно 3, младшая цифра 0, а старшая цифра 12; затем рассмотрим цифру десятков, в это время curr равно 2, младшая цифра равно 3, а старший разряд равен 1. Другие числа могут быть аналогичны, и код реализации выглядит следующим образом:
/**
* 1-N正整数中1的个数
*/
int numOfOne(int n)
{
int factor = 1, cnt = 0; //factor为乘数因子
int low = 0, curr = 0, high = 0;
while (n / factor != 0) {
low = n - n/factor * factor; //low为低位数字，curr为当前考虑位的数字，high为高位数字
curr = n/factor % 10;
high = n/(factor * 10);
switch(curr) {
case 0: //当前位为0的情况
cnt += high * factor;
break;
case 1: //当前位为1的情况
cnt += high * factor + low + 1;
break;
default: //当前位为其他数字的情况
cnt += (high+1) * factor;
break;
}
factor *= 10;
}
return cnt;
}
4 и последовательность натуральных чисел N
вопрос:Введите положительное целое число N и выведите все последовательности, сумма которых равна N последовательным положительным целым числам. Например, введите 15, так как1+2+3+4+5=4+5+6=7+8=15, поэтому выведите 3 последовательные последовательности 1-5, 4-6 и 7-8.
Решение 1. Примените математические законы
Предположим, что существует k последовательных положительных целых чисел, сумма которых равна N, где первое число последовательной последовательности равно x, тогда существуютx+(x+1)+(x+2)+...+(x+k-1) = N. чтобы его можно было получитьx = (N - k*(k-1)/2) / k. когдаx<=0, это означает, что больше нет положительной целочисленной суммы последовательностей для N, и цикл завершается в это время. Инициализируйте k = 2, указав, что сумма 2 последовательных положительных целых чисел равна N, тогда значение x может быть получено, и судят, есть ли 2 последовательных положительных целых числа, начинающихся с x, и сумма равна N, если нет, k ++ , и продолжить цикл.
/**
* 查找和为N的连续序列
*/
int findContinuousSequence(int n)
{
int found = 0;
int k = 2, x, m, i; // k为连续序列的数字的数目，x为起始的值，m用于判断是否有满足条件的值。
while (1) {
x = (n - k*(k-1)/2) / k; // 求出k个连续正整数和为n的起始值x
m = (n - k*(k-1)/2) % k; // m用于判断是否有满足条件的连续正整数值
if (x <= 0)
break; // 退出条件，如果x<=0，则循环退出。
if (!m) { // m为0，表示找到了连续子序列和为n。
found = 1;
printContinuousSequence(x, k);
}
k++;
}
return found;
}
/**
* 打印连续子序列
*/
void printContinuousSequence(int x, int k)
{
int i;
for (i = 0; i < k; i++) {
printf("%d ", x++);
}
printf("\n");
}
Решение 2. Метод последовательного конечного положения
Поскольку в последовательности есть по крайней мере два числа, вы можете сначала определить, равна ли сумма непрерывной последовательности, оканчивающейся на число 2, n, затем равна ли сумма непрерывной последовательности, оканчивающейся на число 3, n, и, таким образом, на. В сообщении в блоге г-на Хэ Хайтао, на которое ссылается эта идея решения, код выглядит следующим образом:
/**
* 查找和为N的连续序列-序列结尾位置法
*/
int findContinuousSequenceEndIndex(int n)
{
if (n < 3) return 0;
int found = 0;
int begin = 1, end = 2;
int mid = (1 + n) / 2;
int sum = begin + end;
while (begin < mid) {
if (sum > n) {
sum -= begin;
begin++;
} else {
if (sum == n) {
found = 1;
printContinuousSequence(begin, end-begin+1);
}
end++;
sum += end;
}
}
return found;
}
Расширение:Можно ли разложить все положительные целые числа на последовательности последовательных положительных целых чисел?
Отвечать:нет. Не все положительные целые числа можно разложить на последовательные положительные целые числа, например, 32 нельзя разложить на последовательные положительные целые числа. Для нечетных чисел мы всегда можем написать2k+1, поэтому его можно разложить на[k,k+1], поэтому его всегда можно разложить на последовательность последовательных положительных целых чисел. Для каждого четного числа его можно разложить на произведение простых множителей, то есть n = 2i * 3j * 5k..., если j, k... все равны 0, кроме i, то n = 2i, для такого числа все его делители четны, непрерывной суммы подпоследовательностей n не существует, поэтому все, кроме степеней 2n>=3Все положительные целые числа можно представить в виде суммы последовательных натуральных чисел.
5 Максимальное количество последовательных подпоследовательностей и
вопрос:Найдите сумму самых больших последовательных подпоследовательностей в массиве, например, данный массивA = {1， 3， -2， 4， -5}, то максимальная сумма последовательных подпоследовательностей равна 6, то есть1 + 3 +（-2）+ 4 = 6.
анализировать:Проблема максимальной суммы последовательных последовательностей — очень старый вопрос на собеседовании, и лучшее решение —O(N)Сложность, конечно, заслуживает внимания. Здесь приведены три распространенных решения, основное внимание уделяется последнему.O(N)решение может быть. Следует отметить, что если максимальная сумма последовательных подпоследовательностей в некоторых вопросах отрицательна, она вернет 0; если все вопросы в этом вопросе отрицательные, будет возвращено наибольшее отрицательное число.
Решение 1:Поскольку наибольшая последовательная сумма подпоследовательностей может начинаться только с позиции в массиве от 0 до n-1, мы можем перебирать позиции от 0 до n-1 и вычислять максимальное значение среди всех сумм последовательных подпоследовательностей, начинающихся с этой позиции. Наконец, можно получить максимальное значение.
/**
* 最大连续子序列和
*/
int maxSumOfContinuousSequence(int a[], int n)
{
int max = a[0], i, j, sum; // 初始化最大值为第一个元素
for (i = 0; i < n; i++) {
sum = 0; // sum必须清零
for (j = i; j < n; j++) { //从位置i开始计算从i开始的最大连续子序列和的大小，如果大于max，则更新max。
sum += a[j];
if (sum > max)
max = sum;
}
}
return max;
}
Решение 2:Проблема также может быть решена методом «разделяй и властвуй», когда максимальные суммы последовательных подпоследовательностей появляются либо в левой половине массива, либо в правой половине массива, либо в обеих половинах. Следовательно, максимальная сумма последовательных подпоследовательностей может быть получена путем нахождения максимального значения в этих трех случаях.
/**
* 最大连续子序列和-分治法
*/
int maxSumOfContinuousSequenceSub(int a[], int l, int u)
{
if (l > u) return 0;
if (l == u) return a[l];
int m = (l + u) / 2;
/*求横跨左右的最大连续子序列左半部分*/
int lmax = a[m], lsum = 0;
int i;
for (i = m; i >= l; i--) {
lsum += a[i];
if (lsum > lmax)
lmax = lsum;
}
/*求横跨左右的最大连续子序列右半部分*/
int rmax=a[m+1], rsum = 0;
for (i = m+1; i <= u; i++) {
rsum += a[i];
if (rsum > rmax)
rmax = rsum;
}
return max3(lmax+rmax, maxSumOfContinuousSequenceSub(a, l, m),
maxSumOfContinuousSequenceSub(a, m+1, u)); //返回三者最大值
}
Решение 3:Есть лучшее решение, просто нужноO(N)время. Поскольку наибольшая непрерывная сумма подпоследовательности возможна только по позиции0～n-1заканчиваться где-то в . Когда i-й элемент пройден, оценивается, больше ли сумма последовательных подпоследовательностей, предшествующих ему, чем 0. Если она больше 0, сумма наибольшей последовательной подпоследовательности, заканчивающейся в позиции i, является суммой элемента i и предшествующие последовательные подпоследовательности; в противном случае сумма наибольших последовательных подпоследовательностей, заканчивающихся в позиции i, равна a[i].
/**
* 最打连续子序列和-结束位置法
*/
int maxSumOfContinuousSequenceEndIndex(int a[], int n)
{
int maxSum, maxHere, i;
maxSum = maxHere = a[0]; // 初始化最大和为a[0]
for (i = 1; i < n; i++) {
if (maxHere <= 0)
maxHere = a[i]; // 如果前面位置最大连续子序列和小于等于0，则以当前位置i结尾的最大连续子序列和为a[i]
else
maxHere += a[i]; // 如果前面位置最大连续子序列和大于0，则以当前位置i结尾的最大连续子序列和为它们两者之和
if (maxHere > maxSum) {
maxSum = maxHere; //更新最大连续子序列和
}
}
return maxSum;
}
6 Максимальный последовательный продукт последовательности
вопрос:Учитывая последовательность целых чисел (возможно, положительных, 0 и отрицательных), найдите произведение одной из ее наибольших последовательных подпоследовательностей. Например, дан массивa[] = {3, -4, -5, 6, -2}, то максимальный последовательный продукт подпоследовательности равен 360, то есть3*(-4)*(-5)*6=360.
развязать:Нахождение произведения наибольшей непрерывной подпоследовательности отличается от задачи наибольшей суммы непрерывной подпоследовательности, потому что есть положительные и отрицательные значения и могут быть 0. Это может быть решено непосредственно с помощью динамической регрессии.Учитывая, что могут быть отрицательные числа, мы используйте max[i] для представления значения произведения наибольшей непрерывной подпоследовательности, оканчивающейся на a[i], и используйте min[i] для представления значения произведения наименьшей непрерывной подпоследовательности, оканчивающейся на a[i], тогда уравнение перехода состояния является:
max[i] = max{a[i], max[i-1]*a[i], min[i-1]*a[i]};
min[i] = min{a[i], max[i-1]*a[i], min[i-1]*a[i]};
Начальное состояниеmax[0] = min[0] = a[0]. код показывает, как показано ниже:
/**
* 最大连续子序列乘积
*/
int maxMultipleOfContinuousSequence(int a[], int n)
{
int minSofar, maxSofar, max, i;
int maxHere, minHere;
max = minSofar = maxSofar = a[0];
for(i = 1; i < n; i++){
int maxHere = max3(maxSofar*a[i], minSofar*a[i], a[i]);
int minHere = min3(maxSofar*a[i], minSofar*a[i], a[i]);
maxSofar = maxHere, minSofar = minHere;
if(max < maxSofar)
max = maxSofar;
}
return max;
}
7-битная корреляция
1) Определить, является ли натуральное число целой степенью числа 2.
вопрос:Для заданного положительного целого числа n определите, является ли это положительное целое число степенью числа 2.
Решение 1:Основное решение состоит в том, чтобы установитьi=1Начните, цикл умножая на 2, покаi>=n, а затем определить, равно ли i n.
Решение 2:Есть и лучший способ, который состоит в том, чтобы посмотреть на двоичное представление числа, как вn=101000, то мы можем найтиn-1=100111. то естьn -> n-1Он состоит в том, чтобы заменить крайнюю правую единицу числа n на 0 и одновременно изменить все биты справа от крайней правой единицы числа n с 0 на 1. Следовательно, еслиn & (n-1) == 0Можно определить, что натуральное число n является целой степенью числа 2.
/**
* 判断正整数是2的幂次
*/
int powOf2(int n)
{
assert(n > 0);
return !(n & (n-1));
}
2) Найдите количество единиц в двоичном представлении целого числа
вопрос:Найдите количество единиц в двоичном представлении целого числа. Например, при N = 6 его двоичное представление равно 0110, а количество единиц в двоичном представлении равно 2.
Решение 1:Естественный подход состоит в том, чтобы выполнить побитовое И N и 1, а затем разделить N на 2, пока N не станет равным 0. Код алгоритма выглядит следующим образом:
int numOfBit1(int n)
{
int cnt = 0;
while (n) {
if (n & 1)
++cnt;
n >>= 1;
}
return cnt;
}
Существует проблема с приведенным выше кодом. Если ввод отрицательный, это вызовет бесконечный цикл. Чтобы решить проблему отрицательных чисел, если вы используете JAVA, вы можете напрямую использовать беззнаковый оператор сдвига вправо >>> чтобы решить ее.Если это в C/ В C++, чтобы избежать бесконечного цикла, мы не можем сдвигать входное число i вправо. во-первыхi & 1, определите, равен ли младший бит i 1. Затем сдвиньте 1 влево на один бит, чтобы получить 2, а затем выполните операцию И с i, чтобы определить, равен ли 1 второй старший бит i.
/**
* 二进制表示中1的个数-解法1
*/
int numOfBit1(int n)
{
int cnt = 0;
unsigned int flag = 1;
while (flag) {
if(n & flag)
cnt++;
flag = flag << 1;
if (flag > n)
break;
}
return cnt;
}
Решение 2:Лучшее решение — каждый раз следовать одному и тому же ходу мыслей в первом вопросе.n&(n-1)Он может изменить крайнюю правую единицу в n на 0, поэтому легко найти общее количество единиц.
/**
* 二进制表示中1的个数-解法2
*/
int numOfBit1WithCheck(int n)
{
int cnt = 0;
while (n != 0) {
n = (n & (n-1));
cnt++;
}
return cnt;
}
3) Инвертировать все биты целого числа без знака
вопрос:Дано целое число без знака N, инвертировать все биты целого числа. Например, есть восьмизначное число.01101001, то после инверсии становится10010110, инверсия 32-битного целого числа без знака аналогична.
Решение 1:Естественным решением является обращение к алгоритму инверсии строки.Предполагая, что беззнаковое целое имеет n бит, сначала поменять местами 0-й бит с n-м битом, а затем поменять местами 1-й бит с n-1-м битом... Обратите внимание, что обмен Два бита могут быть достигнуты с помощью XOR, потому что0 XOR 0 = 0, 1 XOR 1 = 0, 0 XOR 1 = 1, 1 XOR 0 = 1, операция XOR 0/1 с 1 инвертирует его значение.
/**
* 反转比特位
*/
uint swapBits(uint x, uint i, uint j)
{
uint lo = ((x >> i) & 1); // 取x的第i位的值
uint hi = ((x >> j) & 1); // 取x的第j位的值
if (lo ^ hi) {
x ^= ((1U << i) | (1U << j)); // 如果第i位和第j位值不同，则交换i和j这两个位的值，使用异或操作实现
}
return x;
}
/**
* 反转整数比特位-仿字符串反转
*/
uint reverseXOR(uint x)
{
uint n = sizeof(x) * 8;
uint i;
for (i = 0; i < n/2; i++) {
x = swapBits(x, i, n-i-1);
}
return x;
}
Решение 2:Используя стратегию «разделяй и властвуй», сначала поменяйте местами соседние биты числа x, затем 2 бита, затем 4 бита... например, дано 8-значное число.01101010, то соседние биты сначала меняются местами, чтобы стать10 01 01 01, затем поменяйте местами соседние 2 бита, чтобы получить01 10 01 01, а затем 4-битный обмен, чтобы получить0101 0110. Общая временная сложностьO(lgN), где N — количество цифр в целом числе. Вот код для обращения 32-битного целого числа и т. д., если целое число 64-битное.
/**
* 反转整数比特位-分治法
*/
uint reverseMask(uint x)
{
assert(sizeof(x) == 4); // special case: only works for 4 bytes (32 bits).
x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2);
x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4);
x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8);
x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16);
return x;
}
использованная литература
- Красота программирования
- конкретная математика
- статьи.Ли TCO.com/reverse-bit…
- Чжэцзянский университет очень хорош.blog.163.com/blog/static…