OFF: Прошу подключиться к решению загадки… — II (Страница 2 из 3)

Это решение лучше .

The gray Cardinal
Мне кажется, ты неверно решил. У девятки должен быть хвостик, то есть 9 это просто перевернутая 6.

офф: ну вот...опять ответы подсмотрели

Дружище, так это рекорд!
http://math.all-tests.ru/node/468

Простенькая задачка.
Подсчитать количество битов (1) в 32 битном знаковом числе.

teadrinker, я же говорю - простая задача. Кстати, перед тем как написать ее сам вспоминал ее решение.

Всем, возможно имеет смысл использовать кнопку

ypppu, это Вы сами обнаружили или Вам показали? Там масштабы совершенно разные - на украинской гривне голова Ярослава в половину полотна, возможно это репродукция картины или иконы. На российской тысяче - изображение памятника в Ярославле в полный рост. И повреждение глаза - надо еще умудриться разглядывать в сильную лупу.

К сожалению у меня нет достаточно большой лупы. Сколько смотрел не увидел ничего. Возможно небольшой брак, который в данном случае несущественен.

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

Ну вот, сейчас придёт Aскет, и скажет, что известно кто .

А чем ym.zip открывать то: ни проводник, ни WinRAR его не берут.

У меня извлекает только через восстановление архива. Уже второй раз сталкиваюсь, что с аттача нормально не скачивается.

У меня та же байда. WinRAR 3.80.

Хотя не, вру. WinRAR 3.10 (2002 г).

>kaster
>120,30,30

Ну так это я тебя проверял на внимательность и знание википедии.
Естественно что подразумевалось 60.

У нас, у долбомасонских слявянских этимологов, так принято, всех проверять.

А вот извлечь из него изображения действительно не получается.

Ну-ка, ну-ка… Под Server 2008 R2 — увы.

То есть, сколько знаков в числе, состоящем из 32 знаков?

Раз речь о битах, надо понимать, что число - в двоичной системе, так? Но ведь 32 знаками можно записать много  разных чисел:
00000000000000000000000000000000
00000000000000000000000000000001
00000000000000000000000000000010
. . .
11111111111111111111111111111101
11111111111111111111111111111110
11111111111111111111111111111111
То есть 32-битное число может содержать от 0 до 32 знаков.

Теперь ясно.

Добавлено: А ещё наверно число задаётся в десятичной системе, о чём явно не указано.

..А ведь есть и отрицательные и даже дробные числа при записи в 2х СС.

#!/bin/env python
def bits_calc(n):
    n_in = n
    if n < -2**31 or n > 2**31-1:
        ans = -1
        binrep = 'Number is out of range'
    else:
        if n == 0:
            ans = 0
            binrep = '0'*32
        else:
            sign = '0'
            ans = 0
            binrep = ''
            if n < 0:
                sign = '1'
                n += 2**31
                ans += 1
            while True:
                intp, resp = n//2, n % 2
                binrep = str(resp) + binrep
                if resp == 1:
                    ans += 1
                if intp < 2:
                    binrep = str(intp) + binrep
                    ans += 1
                    break
                n = intp
            binrep = sign + binrep.zfill(31)
    return ans, binrep

n = 2**32
onebitnum, binaryrepresentation = bits_calc(n)
print 'Binary representation of %d: %s\nNumber of one bits: %d' % (n, binaryrepresentation, onebitnum)
n = -128
onebitnum, binaryrepresentation = bits_calc(n)
print 'Binary representation of %d: %s\nNumber of one bits: %d' % (n, binaryrepresentation, onebitnum)

Я не совсем понял этот момент. По твоему нецелые числа состоят не из битов?

Положительный и отрицательный нули, вроде бы, имеют место для машинного представления вещественных чисел. Для представления отрицательных целых чисел обычно используется дополнительный код и в нём нет места для ещё одного нуля, а 111…1 — это минус 1.

Мне кажется, Rumata зря уточнил, что число знаковое, т.к. это ни на что влиять не должно (по крайней мере для битовых операций).
На 32 битах тоже, может быть не стоило бы зацикливаться, а сказать, что длина машинного слова фиксирована и известна. Хотя для некоторых решений это существенно, но, возможно, и их можно было бы обобщить на произвольную длину, хотя я этого сделать не берусь, т.к. сам их плохо (совсем не) понимаю и сомневаюсь, что участники этого форума найдут их самостоятельно.

Да, я намудрил с отрицательными числами. Это неправильно, что числа разного знака но одного модуля имеют практически одинаковое бинарное представлением, за исключением самого левого бита. И да, для предотвращения двоякости в представлении нуля, надо действительно использовать Two's complement а не Ones' complement. Пределы я тоже использовал от Two's complement. Код подправлю чуть позже.

Ну, вот решение (на авторство не претендую), не зависящее от длины машинного слова и (без)знаковости аргумента (если используется дополнительный код):

function OnesCount(n) {
  var s = 0;
  while (n != 0) {
    n = n & (n - 1);
    s++;
  }
  return s;
}

(Хотя, конечно, ответ для каждого отрицательного числа, в отличии от положительных, зависит от количества выделяемых под запоминание числа разрядов, например, для -1 ответ как раз будет равен разрядности.)

Заметил, что вопрос появился почти одновременно с этой темой.

Я в школе считал вот так

И лучше выдумать не мог. (c)

Память имеет свойство искажаться...
На самом деле я считал вот так:

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

Уточню. Существенно быстрее для неотрицательных чисел. Цикл выполняется ровно M раз, где M - количество взведенных битов (1). В худшем случае (для N = -1) будет выполнено 32 итерации. Видимо можно улучшить этот алгоритм, например, взятием дополнения числа ~N, подсчетом его битов в M, а потом для отрицательных чисел вернуть 32 - M.

Дополнение. Улучшить можно лишь так, чтобы худший результат не превышал 16 итераций.

Я сейчас говорю не о целесообразности такой оптимизации. Это просто академический интерес. Трата времени в свое удовольствие (=

wisgest
Самое большое 32-битное положительное число - 0x7FFFFFFF (31 бит)
Самое большое 32-битное отрицательное число - 0xFFFFFFFF (или -1, 32 бита)

В обоих случаях быстрее и проще посчитать количество битов инвертировал каждый бит:
~0x7FFFFFFF = 0x80000000 (M = 1 бит)
~0xFFFFFFFF = 0x00000000 (M = 0 бит)
затем 32 - M - реальное число бит в исходном числе.

Для чисел вида 0xFFFF0000 и 0x0000FFFF решением является результат 16. Это максимальное количество итераций если попытаться оптимизировать вычисления в цикле. Однако мои оценки для JScript практически не дают существенного выигрыша. Для других языков не проверял.

Совсем я заскучал, поэтому напишу подробное решение.

a = 1985927312; // наше число
n = (a>>1) & 0xDB6DB6DB;
a = a - n;
n = (a>>1) & 0xDB6DB6DB;
a = a - n;
a = ((a + (a>>3)) & 0xC71C71C7) % 63;

Этот алгоритм имеет константное время, а вот алгоритм wisgest'а зависит от количества единичных битов - чем их меньше, тем быстрее код отработает. Так что если известно, что во входном значении почти нет единичных битов или наоборот почти нет нулевых битов, то лучше использовать именно тот алгоритм.

А магические числа это:

const_01 = (-1)/3
const_0011 = (-1)/5
const_00001111 = (-1)/17

деление беззнаковое.
ещё задачки есть или продолжим эту раскрывать?

Ну количества букв явно не достаточно, коллизий будет больше чем совпадений. Тут несколько вариантов и они зависят от размера хеша. Можно поставить каждой букве в соответствие биты в хеше, т.е. чтобы каждая буква влияла только на свои биты, своеобразный аналог сжатия с потерями. На вскидку, при таком подходе размер хеша должен быть раза в два больше алфавита(т.е. в среднем на одну букву должно приходится 2 бита). Можно сделать по аналогии с криптографическими хешами, это универсальный вариант и вероятность коллизии и размер хеша не будут особо зависеть от алфавита.

???

Ничего. Нет. Мы же не подсчитываем анаграммы, а находим. Если не сохранить позицию, то при выдаче результата придётся искать слова по их хешу. Это довольно накладно, лучше потратить на это немного памяти.

Больше всего памяти потребуется, если в словаре нет анаграмм:

• память на хеши - в простейшем случае, если за хеш принят упорядоченный набор букв, составляющих слово, она равна размеру словаря. Иначе размер_хеша*количество_слов.

• память на слова, соответствующие хешам, сами слова хранить очень накладно, поэтому хранят смещения в файле. В простейшем случае используется список - 8 байт на само смещение, ещё 8 на указатель к следующему элементу и 8 на указатель на первый(он же единственный) элемент. Предполагается, что система 64-битная.

Проще, но хуже.

Об этом я в первом ответе написал, а вы ответили:

Тут количество букв не используется, используются сами буквы.

Оба знакомы и оба далеки, Perl чуть дальше . Может си? И прилагается ли словарь для тестирования? .

О чём тут речь?

И возвращаясь к предыдущей задачке - тыц. 9-битный вариант можно преобразовать в 8-битный для 32-битного регистра. Есть аналогичный код для 15-ти бит и 64-битного регистра. Правда оригинальную задачу они не особо хорошо решают .

Тут дело не в синтаксисе, просто на практике проверить скорость не получится. Сишный компилятор сгенерирует очень быстрый код в сравнении со скриптом.

Спасибо, нашёл на виртуалке . Только там какие-то левые слова находятся, например "?ngstr?m" в файле "british-english" O_o. Движок форума даже буквы такие отказывается показывать .

Отлично решает упрощённую задачу, но это не получается использовать для более выгодного решения основной задачи.

И чем тогда интересна эта задача? Простое решение любой школьник найдёт.

Не думаю, вся латиница там верно показана, буква определённо из другого алфавита. Похоже это слово "angstrom" по-шведски написано.

kaster, так отчасти было и на старой версии движка. Даже приходилось паковать код и выкладывать на стороннем ресурсе.

Рекомендую ЕГЭ по математике, там кроме простых решений ничего не требуется. Под интересными задачами я понимаю задачи, как минимум требующие неочевидных решений.

Ну да, если это школа для детей с ЗПР, то у них с этим будут проблемы .

Показать моё что? Если решение этой задачи, то теперь не вижу смысла - тебя оно не интересует, а больше в обсуждении никто не участвует.
P.S. предлагаю общаться на "ты", а то как-то странно получается .

Я всё-таки за обсуждение алгоритма. Если в словаре будет много длинных слов, то их сортировка займёт много времени и памяти, либо придётся сортировать по мере считывания строки. Если же придумать нормальный хеш, то памяти будет требоваться фиксированное количество на слово, плюс его гораздо удобнее сравнивать чем строку. По идее 64-битного хеша должно быть достаточно, но простейший вариант:

BYTE HASH_TABLE[] = {0, 3, 5, 7, 10, 14, 16, 18, 21, 24, 26, 28, 31, 33, 36, 39, 41, 43, 46, 49, 52, 54, 56, 58, 60, 62};
#define HASH_FUNC(hash, x) hash += 1ull<<HASH_TABLE[x-'a']

дал сразу две коллизии на словаре в 100'000 слов. При этом на реальном, упорядоченном словаре он отработал на 10% быстрее и на столько же меньше съел памяти. А вот на случайных данных не было коллизий и отработал на 40% быстрее. На больших выборках не проверял, поскольку этот хеш не годится.

//hash - строка, hash.begin() - итератор на начало строки, hash.end() - итератор на конец строки
std::sort(hash.begin(), hash.end());

Но как я уже сказал - это не "коротко и красиво", а "медленно и банально". И строго говоря это не хеш, у хеша фиксированная длина.

2+2/3 мин, хотя сомневаюсь, однако.

Давайте посмотрим, может есть другие варианты.

Если быть точным, t найдено верно, а вот скорости не определены.

Они могут быть любыми

Ну вот ты приравниваешь все уравнения к одному. С таким же успехом можно приравнять к 10, время останется тем же, скорости изменятся.

А 1 — это чего один?

Так расстояние (объём или масса торта) может быть любым

Причём тут масса? Расстояние - это количество пирогов(или тортов, забыл уже).

всё там правильно, откуда вы вообще килограммы взяли?

нет, скорость в "тортах в минуту" . Я это в решении написал, только про пироги.
З.Ы. Теперь я хочу пирог... Ушёл в магазин полвторого ночи...
upd:

можно, тогда будет 4 переменных на три уравнения, но три интересующие нас переменные всё равно будут определены.

Ну, пирог ты сам придумал

У меня такой алгоритм получился:

MsgBox, % KillSecond(18)

KillSecond(n)
{
   min := 1, max := n
   del := 1   ; удалялось ли последнее число в ряду в предыдущей итерации, в начале равно 1
   step := 1  ; шаг "прореживания"

   Loop  ; цикл
   {
      step *= 2
      
   ; если в прошлой итерации последнее удалялось, минимальное остаётся
   ; иначе заменяется на следующее по предыдущему шагу
      min := del ? min : min + step//2
      
      if (min + step > max)
         break

   ; если разность максимального и минимального делится на шаг с остатком
   ; максимальное заменяется на предыдущее, иначе остаётся
      if mod(max - min, step)
         max -= step//2, del := 1
      else
         del := 0
   }
   Return min
}

Наверное, как-то проще можно