Написать пост

Задача на операцию с битами

Аватар Дмитрий Юрченко

Имеется целое число, в котором можно изменить ровно один бит из 0 в 1. Напишите код для определения длины самой длинной последовательности единиц, которая может быть при этом получена.

Обложка поста Задача на операцию с битами

Условие задачи

Имеется целое число, в котором можно изменить ровно один бит из 0 в 1. Напишите код для определения длины самой длинной последовательности единиц, которая может быть при этом получена.

Пример:
Ввод: 1775 (или 11011101111).
Вывод: 8.

Решение

Любое целое число может рассматриваться как последовательность чередующихся 1 и 0. Если последовательность 0 имеет длину 1, появляется потенциальная воз­можность слияния соседних последовательностей 1.

Метод «грубой силы»

Целое число можно преобразовать в массив, отражающий длины последователь­ностей 0 и 1. При наличии такого массива мы просто перебираем его элементы. Для каждой последовательности 0 рассматривается возможность слияния соседних последо­вательностей 1, если последовательность 0 имеет длину 1.

			import java.util.ArrayList;

public class QuestionB {
	
	public static int longestSequence(int n) {
		if (n == -1) return Integer.BYTES * 8;
		ArrayList sequences = getAlternatingSequences(n);
		return findLongestSequence(sequences);
	}	
	
	/* Получение списка размеров последовательностей . Первая
         * последовательность всегда состоит из 0 (и может иметь нулевую длину),
         * а далее следуют длины чередующихся последовательностей 1 и 0.*/
	public static ArrayList getAlternatingSequences(int n) {
		ArrayList sequences = new ArrayList();
		
		int searchingFor = 0;
		int counter = 0;
		
		for (int i = 0; i < Integer.BYTES * 8; i++) {
			if ((n & 1) != searchingFor) {
				sequences.add(counter);
				searchingFor = n & 1; // Переключение 1 в 0 или 0 в 1
				counter = 0;	
			}
			counter++;
			n >>>= 1;
		}
		sequences.add(counter);
		
		return sequences;
	}
	/* Для заданных длин чередующихся последовательностей 0 и 1
         * найти самую длинную, которую можно построить. */
	public static int findLongestSequence(ArrayList seq) {
		int maxSeq = 1;
		
		for (int i = 0; i < seq.size(); i += 2) {
			int zerosSeq = seq.get(i);
			int onesSeqRight = i - 1 >= 0 ? seq.get(i - 1) : 0;
			int onesSeqLeft = i + 1 < seq.size() ? seq.get(i + 1) : 0;
			
			int thisSeq = 0;
			if (zerosSeq == 1) { // Возможно слияние
				thisSeq = onesSeqLeft + 1 + onesSeqRight; 
			} if (zerosSeq > 1) { // Добавить нуль с любой из сторон
				thisSeq = 1 + Math.max(onesSeqRight, onesSeqLeft);
			} else if (zerosSeq == 0) { // Выбрать с любой стороны
				thisSeq = Math.max(onesSeqRight, onesSeqLeft);
			}
			maxSeq = Math.max(thisSeq, maxSeq);
		}
		
		return maxSeq;
	}	
	
	public static void main(String[] args) {
		int original_number = 1775;
		int new_number = longestSequence(original_number);
			
		System.out.println(Integer.toBinaryString(original_number));
		System.out.println(new_number);				
	}

}
		

Решение получается довольно эффективным. Оно требует затрат времени O(b) и затрат памяти O(b), где b  — длина последовательности. Подробнее об оценке сложности алгоритмов вы можете прочитать в нашей статье.

Будьте внимательны с выражением времени выполнения. Например, если сказать, что время вы­полнения равно О(n), что есть n? Было бы неправильно утверждать, что алгоритм имеет сложность О(целое значение): он имеет сложность О(количество битов). По этой причине, если использование n создает потенциальную неоднозначность, лучше не использовать эту запись, чтобы не путаться самому и не путать интервьюера. Выберите другое имя переменной (мы выбрали b, от слова «bits»).

Возможно ли получить лучший результат? В данном случае читать последователь­ность приходится всегда, поэтому оптимизировать решение по времени не удастся. С другой стороны, можно сократить затраты памяти.

Оптимальный алгоритм

Чтобы сократить затраты памяти, обратите внимание на то, что нам не нужно постоянно хранить длину каждой последовательности. Она должна храниться столько времени, сколько необходимо для сравнения каждой последовательности 1 с предшествующей ей последовательностью 1.

Следовательно, мы можем ограничиться отслеживанием длин текущей и предыду­щей последовательности 1. При обнаружении нулевого бита происходит обновление предыдущей длины previousLength:

  • Если следующий бит содержит 1, previousLength присваивается currentLength;
  • Если следующий бит содержит 0, выполнить слияние последовательностей невозможно, поэтому previousLength присваивается 0.

Значение maxLength обновляется в процессе перебора.

			public class QuestionD {

	public static int flipBit(int a) {
		/* Если а содержит только 1, это уже самая длинная последовательность */ ;
		if (~a == 0) return Integer.BYTES * 8;
		
		int currentLength = 0;
		int previousLength = 0;
		int maxLength = 1; // Всегда может быть последовательность, содержащая не менее одной 1
		while (a != 0) {
			if ((a & 1) == 1) {
				currentLength++;
			} else if ((a & 1) == 0) {
				/* Присвоить 0 ( следующий бит равен 0) или currentLeпgth ( следующий бит равен 11) . */
				previousLength = (a & 2) == 0 ? 0 : currentLength;
				currentLength = 0;
			}
			maxLength = Math.max(previousLength + currentLength + 1, maxLength);
			a >>>= 1;
		}
		return maxLength;
	}
	
	public static void main(String[] args) {
		int[][] cases = {{-1, 32}, {Integer.MAX_VALUE, 32}, {-10, 31}, {0, 1}, 
				{1, 2}, {15, 5}, {1775, 8}};
		for (int[] c : cases) {
			int x = flipBit(c[0]);
			boolean r = (c[1] == x);
			System.out.println(c[0] + ": " + x + ", " + c[1] + " " + r);
		}

	}

}
		

Время выполнения этого алгоритма также равно О(b), но объем дополнительной памяти сокращается до О(1).

Если вы решили данную задачу, попробуйте реализовать функцию, определяющую количество битов, которое необходимо изменить, чтобы из целого числа А получить целое число B. Решение найдете здесь.

Следите за новыми постами
Следите за новыми постами по любимым темам
7К открытий7К показов