Xeroxed
@Xeroxed
Senior javascript developer

Как найти подряд три идущих единицы с использованием битовой логики?

Каким способом и или алгоритмом можно найти три подряд идущих единицы с использованием побитовой логики? Если можно, то с учётом как горизонтального, так и вертикального ряда.

var Map = [
  [0, 0, 1, 1, 1, 0, 0, 1],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0, 0]
];
  • Вопрос задан
  • 1439 просмотров
Пригласить эксперта
Ответы на вопрос 6
SynCap
@SynCap
Делаю интернет с 1998 года
Судя по всему задание - учебное, задание, скорее всего, составлял спец по алгоритмам. Поэтому готового решения задачи приводить не буду, а дам подсказки.

1. Массив Map можно конвертировать в массив байтов или просто рассматривать каждую строку, как массив битовых значений, соответствующих байту.
Внешним циклом на этом этапе, будет перебор строк.
В таком случае можно применять битовую логику:
byteVal = Map[idx][0]*128+ Map[idx][1]*64+ Map[idx][2]*32+ Map[idx][3]*16+ Map[idx][4]*8+ Map[idx][5]*4+ Map[idx][6]*2+Map[idx][7]*1;


Где idx - это номер проверяемой циклом строки. Кстати, для совсем кошерного программирования, правильнее будет вычислять byteVal также в цикле, заменив фиксированные значения во вторых квадратных скобках на другой индекс (позиции), а множитель - это все числа, которые можно представить степенью двойки, используя лишь один байт с одним установленным битом на всех возможных позициях.
Как с помощью битовых операций получать в цикле такие числа, смотри в примере кода ниже.

2. теперь, последовательно сравним byteVal с числами, содержащими подряд 3 единицы в битовом выражении. Таких чисел, будет всего 6(!) - поиграйтесь с калькулятором, чтобы убедиться.
Это можно записать в одну операцию (чисел для сравнения небольшое количество, их легко подготовить с помощью калькулятора и назначить константам), либо использовать операцию сдвига, взяв за основу число 7, которое есть 7 и одинаково 7 и в 8ми, и в 10ти, и в 16ти разрядных записях - все-равно: 7 = 0x7 = 0o7, и все остальные, нужные для тестирования значения получать в цикле используя побитовый сдвиг.
Т.е. внутри цикла перебора строк, после вычисления значения байта:

var testVal = 7;

for (var i = 0; i < 6 OR ; i++) {
    if ( profit = byteVal & testVal === testVal )
        console.log('Profit найден в позиции %i', 6-i);
   testVal <<= 1;  // то же, что и возведение 2 в следующую степень
}


UPD: кого-то может удивить, а где оптимизация сдвига? дело в том, что принцип необходимо и достаточно, никто не отменял. Для слишком длинных строк, такой способ непременим - ограничение размера сдвига для Javascript - 32.
Для вычисления актуального размера сдвига нужно ГОРАЗДО больше операций, чем лишние пару циклов с побитовым сравнением. Это справедливо даже для ассемблера, а для любой реализации Javascript в частности - ваабче в 100500 раз. Мы уже на каждой итерации внешнего цикла в данном шаге экономим пару циклов.

Код приведен в соответствие со стандартами ECMA262 (ES5), новых фишек ES6 (ES2015) в нем нет.

3. Внешний цикл, в отличие от предыдущего шага, лучше будет сделать - для тестового значения. Внутренний цикл - для номера строки, начинающей блок сравнения, состоящий из 3 смежных строк - для просмотра, совпадений по вертикали, проходим циклом по строкам 6(!) раз, вычисляем byteVal для каждой из 3х строк блока сравнения, будем проверять значения на совпадение одного бита, т.е. начальное значение testVal = 1, сдвигать влево, тоже будем на 1 бит.
Для оптимизации алгоритма, будем сравнивать сначала byteVal для 1й тестируемой строки, если не совпадает, сразу увеличиваем индекс начальной строки на 1 и уходим на следующий шаг, иначе - (если 1е сравнение == profit) сравнение второй строки набора сравнения, если неудачно - прибавляем к индексу 2, а если сравнение неудачно только на 3й строке - 3, и соответственно - следующий шаг сравнений.
Оптимизация заключается в том, что мы пропускаем комбинации строк, где заведомо не будет подряд значений. Т.е. если при проверке 3й строки мы выяснили, что профита не светит, то мы начинаем проверку, со следующей строки, но считаем ее первой строкой проверяемого набора, т.е. сдвигаем указатель начала проверяемого блока сразу на 3 позиции, т.к. последовательная проверка блоков со смещением +1 и +2 - заведомо не дадут профита, т.к. мы уже точно знаем, что на этом участке с профитом - облом.

4. Второй вариант решения по нахождению совпадений по столбцам - это транспонировать ("развернуть" массив, сделав строки столбцами) массив Map, и к нему применить шаги 1 и 2. Либо относиться к нему как к заведомо транспонированному, заменив перебор строк, на перебор позиций, тогда при вычислении byteVal, каждое Map[idx][x], заменить на Map[x][idx].

Подробнее о битовых операциях на DevDocs.io и на Javascript.ru (по-русски)

По алгоритмам поиска, на основе которого построена оптимизация поиска, советую почитать Дональд Кнут "Сортировка и поиск", либо Томас Кормэн и др. "Алгоритмы. Построение и анализ".

P.S.: Честно говоря, на написание рабочего решения, мне понадобилось, в 20(!) раз меньше времени и раз в 5 меньше текста. Цените ленивые неучи, для вас старался, а то помрет старая гвардия и ваши рабочие места займут старательные индусы и дотошные китайцы!

UPD2: в литературе по графике, распознаванию образов и еще каким-то анализаторами, такие задачи встречаются, как части, только массивы данных дец поширше, и знаааачительно подлиннее.
Ответ написан
Комментировать
romy4
@romy4
Exception handler
А что вам мешает "в лоб" сравнивать три подряд элемента в массиве и сдвигаться на один следующий?
Ответ написан
abyrkov
@abyrkov
JavaScripter
var l = Map.length;
var l2 = Map[0].length;
for(var i = 0; i < l; i++) {
  var el = Map[i];
  for(var i2 = 0; i2 < l2; i2++) {
    if(el[i2] != 0) {
      if(el[i2 + 1] != 0 && el[i2 + 2] != 0); //Нашли
      if(Map[i + 1][i2] != 0 && Map[i + 2][i2] != 0;); //Нашли
    }
  }
}

Логика, думаю, понятна: мы ищем единицы, только если мы нашли единицу.

PS Можно еще сильнее оптимизировать, но у меня уже глаза болят)
Ответ написан
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
ee7d95d214184285aa28c2d0f1c98cf7.jpg
Мой велосипед на PHP (с алгоритмом оптимизированного поиска):
<?php
error_reporting	(E_ALL); // включаем лог ошибок

function array_flatten($array) {
   $return = array();
   foreach ($array as $key => $value) {
       if (is_array($value)){ $return = array_merge($return, array_flatten($value));}
       else {$return[$key] = $value;}
   }
   return $return;
}

function rotate90($array) {
  array_unshift($array, null);
  $array = call_user_func_array('array_map', $array);
  $array = array_map('array_reverse', $array);
  return $array;
}

$Map = [
  [0, 1, 1, 1, 0, 0, 1, 1],
  [0, 0, 0, 1, 0, 1, 0, 0],
  [1, 0, 1, 0, 0, 0, 0, 1],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0, 1],
  [0, 1, 0, 0, 1, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 1, 1]
];

$Map90 = array_flatten(rotate90($Map));
$Map = array_flatten($Map);

$s='';
$s90='';
foreach ($Map as $k=>$i) {
  $s.=$i;
  $s90.=$Map90[$k];
}

echo $s.'<br>';
echo $s90.'<br>';

 //убрать переносы на след.строку
$i=0;
do {
   $n=strpos($s,'111',$i++);
   if ($n) {
      if($n%8>5) $i=8*(1+floor($n/8));
      else break; //найдено! :)
   } else break; //не найдено :(
} while (-1);

 //убрать переносы на след.строку
$i=0;
do {
   $n90=strpos($s90,'111',$i++);
   if ($n90) {
         if($n90%8>5) $i=8*(1+floor($n90/8));
        else break; //найдено! :)
   } else break; //не найдено :(
} while (-1);

if ($n90!==false) {
   $n90=(8-$n90%8-3)*8+floor($n90/8); //конвертим в верный индекс
   if(!$n||$n&&$n90<$n) $n=$n90; //берём минимальный ближайший к началу.
}

//OUT
if ($n!==false) {
 echo "Позиция в массиве (начиная с 0): ".$n.'<br>'; //позиция первого элемента совпадения в "плоском" массиве.
 echo "Координаты по X*Y в двумерном массиве: ".($n%8).'x'.floor($n/8); //COLxROW
} else echo "не найдено!";
?>
Ответ написан
Daemon23RUS
@Daemon23RUS
Постановка задачи непонятна, вернее то что вы подразумеваете под битовой логикой если это true/false то признак 3х идущих подряд единиц по горизонтали = x[i] AND x[i+1] AND x[i+2] (х=бит)
если строку массива рассматривать как байт, то выражения (x AND 0x07) OR (x AND 0x0E) OR (x AND 0x1C ) OR (x AND 0x38) OR (x AND 0x70) OR (x AND 0xE0) Признак наличия 3х еденичных бит подряд а x[i] AND x[i+1] AND x[i+2] (х=байт и более) признак наличия 3х еденичных бит по вертикали.
Ответ написан
Комментировать
@evgeniy_lm
На любом языке высокого уровня ваша "битовая логика" будет работать медленнее и выглядеть уродливо чем примитивное целочисленное суммирование.
i := 0;
j := 0;
repeat
repeat
s := 0;
for k := 0 to 2 do
s := s + arr[j, i +k];
inc(i);
until (i < 5) and (s > 0) ;
inc(j);
until (j <= High(arr)) and (s > 0) ;
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы