(~n & w) | (n&(w-1))

игрался http://cpp.sh/56gb3

n & (w-1) очень похоже на n%w
но по отдельности это не упростить
может даже не в одну строку а в целую функцию

| Сообщение посчитали полезным:

Правая часть остаток от деления на w, если w степень двойки. У левой арифметический смысл только в том, что среди слагаемых n - степеней 2 нет w, тогда w прибавляется к остатку.

-----
2 оттенка серого

| Сообщение посчитали полезным:

псевдокод ?
а что он делает я и так знаю
построение дерева меркель

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

| Сообщение посчитали полезным:

ставим биты по маске n в слове w по странной зависимости от самого слова w?

(~n & w) | (n & (w-1))

если w-1==0 то w&~n
если w-1==-1 то w|n

|
w 000
n 010
out 010 // always the mask itself?

&
w 001
~n 101
out 001

другие примеры не обдумывал, страшно и безсмысленно

Добавлено спустя 10 минут
ой не ошибка в первом же примере с |, w==000...
но жопой чую это с масками магия, без бранчей в зависимости от w
наверно компиль берёт универсальную формулу эту и подставляет её куда не лень

| Сообщение посчитали полезным:

не странный а обычный merkle tree
вот оригинальный алго с бранчами и интересен

| Сообщение посчитали полезным:

при чём здесь меркле то? меркле хэшики из хэшиков делает, в принципе
а тут одна бинарная операция и как её связывать с "построение дерева меркель" тебе только известно

вот нормальная, не странная версия алго, х bool, ноль или один
(~n & w) | (n & -x)
==
if (x) { w = w | n } // set bits
else { w = w & ~n } // clear bits

а у тебя w-1 вместо -х, вот и думай шо туда попадает
и как на шо влияет

чуть довавив
#if 1
printf("(");
printf("N ");
printb(n);
printf(" W ");
printb(w);
printf(" X ");
printb((~n & w)|(n&(w-1)));
printf(" SET ");
printb((n | w) );
printf(" CLE ");
printb((~n & w) );
//if ( ((n+1) % (w)) != ( (~n & w)|(n&(w-1)) )) printf("NEQ");
printf(") ");
#endif

заметил лишь только то шо длинна маски n не влияет на выход x, он всегда обрезаеца до длины слова w

больше думать не могу но оно уже ближе модуло...

| Сообщение посчитали полезным:

ну так чё какие результаты?

| Сообщение посчитали полезным:

reversecode

Это не бинарная(булева) формула, а аналого-цифровая. Есть операция вычитания, если w не булева переменная, то выражение не известно как свернуть, я такое уже спрашивал --> Link <--

Если бы это был инкремент, то можно было бы использовать закон A - B = NOT(B) + A + 1. Как быть с деком хз.

-----
vx

| Сообщение посчитали полезным:

мне надо не свернуть а наоборот развернуть

| Сообщение посчитали полезным: