?

Log in

No account? Create an account

Вопрос навскидку - Ваши рубидии уже у кобальта во ртути

Oct. 19th, 2011

08:01 pm - Вопрос навскидку

Previous Entry Share Next Entry

С точки зрения математика выражение n - n/2 - n/4 - n/8 - n/16 - ... очевидным образом равно нулю. Быстро и не особенно задумываясь, ответьте, чему оно равно для целых n с точки зрения программиста.

Upd: Правильные ответы повалили валом, расскриниваю.

Comments:

[User Picture]
From:stumari
Date:October 20th, 2011 03:17 am (UTC)
(Link)
"Быстро и не особенно задумываясь" == n
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 20th, 2011 03:22 am (UTC)
(Link)
Почему же?
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:solomon2
Date:October 20th, 2011 03:19 am (UTC)
(Link)
Не определено потому что бесконечный цикл.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 20th, 2011 03:24 am (UTC)
(Link)
Определено, потому что начиная с некоторого, все вычитаемые равны нулю.
(Reply) (Parent) (Thread) (Expand)
(Deleted comment)
[User Picture]
From:spamsink
Date:October 20th, 2011 03:55 pm (UTC)
(Link)
Нет; комменты раскрыты.
(Reply) (Parent) (Thread)
[User Picture]
From:vgramagin
Date:October 20th, 2011 03:25 am (UTC)
(Link)
n/MAXINT
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 20th, 2011 04:46 am (UTC)
(Link)
Нет. Я раскрыл комменты.
(Reply) (Parent) (Thread)
[User Picture]
From:kdv2005
Date:October 20th, 2011 04:00 am (UTC)
(Link)
Сдается мне, что сумме цифр в двоичном разложении числа n
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 20th, 2011 03:54 pm (UTC)
(Link)
Правильно сдается.
(Reply) (Parent) (Thread)
[User Picture]
From:kcmamu
Date:October 20th, 2011 04:02 am (UTC)
(Link)
n<0 -> не определено
n>=0 -> число единичных битов у n
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 20th, 2011 04:48 am (UTC)
(Link)
Языки, в которых для n<0 это выражение не определено, должны быть подвергнуты остракизму. А в которых определено, там, конечно, правильный ответ sign(n)*popcount(abs(n)).
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:scolar
Date:October 20th, 2011 04:08 am (UTC)
(Link)
Количеству единиц в двоичной записи n?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 20th, 2011 04:49 am (UTC)
(Link)
Да.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:burzumka
Date:October 20th, 2011 04:18 am (UTC)
(Link)
количеству единиц в битовом представлении
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 20th, 2011 04:49 am (UTC)
(Link)
Да.
(Reply) (Parent) (Thread)
[User Picture]
From:ramlamyammambam
Date:October 20th, 2011 04:20 am (UTC)
(Link)
Сдвиг вправо?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 20th, 2011 04:36 am (UTC)
(Link)
На сколько?
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:ygam
Date:October 20th, 2011 04:30 am (UTC)
(Link)
Сумма битов, что ли?

(я не особенно задумывался)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 20th, 2011 04:51 am (UTC)
(Link)
Да. В случае отрицательных n - как повезет.
(Reply) (Parent) (Thread)
[User Picture]
From:4da
Date:October 20th, 2011 09:27 am (UTC)
(Link)
Что-то я никак не пойму, почему так получается.
Кто-нибудь может объяснить?

(Reply) (Thread)
[User Picture]
From:4da
Date:October 20th, 2011 09:38 am (UTC)
(Link)
Похоже, я что-то понял.

Число n-n/2 равно n/2, если n - четно и n/2 + 1, если n - нечетно.

Получается, что при последовательном вычитании эти +1 накапливаются и остаются в остатке.

Примерно, так?
(Reply) (Parent) (Thread) (Expand)