просмотра таблицы для подсчета количества установленных битов в Integer

пытается решить этот популярный интервью вопрос - http://www.careercup.com/question?id=3406682 просмотра таблицы для подсчета количества установленных битов в Integer

Есть 2 подхода к этому, что я был в состоянии понять -

Brian Кернигана algo - Bits counting algorithm (Brian Kernighan) in an integer time complexity
Таблица поиска.

Я предполагаю, что, когда люди говорят, что использовать таблицу поиска, они имеют в виду HashMap с Integer в качестве ключа, и подсчет количества установленных битов в качестве значения.

Как построить такую таблицу поиска? Используем ли мы Brian's algo для подсчета количества бит в первый раз, когда мы сталкиваемся с целым числом, помещаем его в хэш-таблицу, а в следующий раз, когда мы сталкиваемся с этим целым, извлекаем значение из hashtable?

PS: Я знаю, что аппаратное и программное обеспечение api доступно для выполнения popcount (Integer.bitCount()), но в контексте этого вопроса интервью нам не разрешено использовать эти методы.

источник

2015-07-08 Quest Monger

Целые числа могут быть непосредственно использованы для индексирования массивов; , например. поэтому у вас есть простой массив беззнаковых 8-битных целых чисел, содержащих счетчик бит-бит для 0x0001, 0x0002, 0x0003 ... и посмотрите на array[number_to_test].

Вам не нужно реализовывать хеш-функцию для сопоставления 16-битного целого с чем-то, что вы можете заказать, чтобы иметь возможность поиска!

источник

2015-07-08 19:50:52

Благодарим за разъяснение этого. Можете ли вы объяснить, как можно было бы в первую очередь определить определение «число бит-бит» для указанных целых чисел? Причина, по которой я спрашиваю об этом, заключается в том, что метод, используемый для определения popcount для таблицы поиска, добавляет к сложности времени всей системы. –

@QuestMonger: Это зависит от того, как вы понимаете вопрос интервью. Но если вы не считаете размер программы частью сложности проблемы, вы просто отправляете предварительно вычисленную таблицу с помощью своей программы. Но в этом весь смысл такие вопросы: можете ли вы обсудить эти моменты? Я действительно вздыхаю на таких сайтах, как тот, который вы цитируете, потому что они считают, что Google рассматривает интервью, например, ваш город относится к экзаменационным вопросам водительских прав: это не так. Возможно, существует несколько приемлемых ответов и интервью - это выяснить, насколько вы понимаете (а не знать наизусть). –

Очень верно. К сожалению, сейчас ситуация с интервью намного хуже, при этом автоматические опросы по скринингу и отсутствие участия человека в конво (hackerrank, codility и т. Д.). Немного об отправке справочных таблиц очень интересно. Я работал в предположении, что мне нужно было все с нуля. Я запомню это. Благодаря! –

Чтобы ответить на ваш вопрос о том, как вычислить эту таблицу:

int table[256] /* For 8 bit lookup */ 
for (int i=0; i<256; i++) { 
    table[i] = table[i/2] + i&1 
}

просмотра этой таблицы на каждом байте данного числа и суммировать полученные значения.

источник

2017-07-01 19:57:03 Vamshi

просмотра таблицы для подсчета количества установленных битов в Integer

ответ

Смежные вопросы