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

Почитать K&R. Задание для лабораторки наверняка по ней составляли :)

Сдвиги использовать можно?

вообще тупо long long a = 0x8000000000000000

> вообще тупо long long a = 0x8000000000000000

именно тупо, нужно использовать uint64_t, или __int64 для Wыn32

Да, чорт, забыл о том, что старший бит может быть нулевым. Вот тупняк

не совсем понятно
0b10101111 & 0b10000000 разве не подходит?

а, большое число...
для long long & нету?

Если я правильно понял ТС, то ему нужно обнулить младшие 8 бит?

return a & (~0xff)

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

return a & ~0x7F

>Если я правильно понял ТС, то ему нужно обнулить младшие 8 бит?

Если я правильно понял задание, то нужно для произвольной наперёд заданной разрядности сбросить все младшие биты.

Иначе бы и вопроса не возникло :)

Я изящного решения в рамках описанной задачи не вижу.

Хотя условия озвучены недостаточно строго, так что может я и ошибаюсь :)

Например, в каком виде подаётся разрядность?

Т.е. биты, после самой старшей единицы?

И что, для 64битного числа проканает?)

Две звезды?

Те «старший» бит на произвольной позиции, или нет?

>Сдвиги использовать можно?

Можно, забыл сказать

>Почитать K&R. Задание для лабораторки наверняка по ней составляли :)

Я уж давно не студент :)

>Те «старший» бит на произвольной позиции, или нет?

На произвольной

>0b10101111 & 0b10000000 разве не подходит?

Нет, потому что

Число от 0 до 2^64-1

(из работающего кода) fw - требуемое число

                int pow2 = 0;
                while(fw != 1){
                        fw >>= 1;
                        pow2++;
                }
                fw = (1 << pow2);

>Если я правильно понял ТС, то ему нужно обнулить младшие 8 бит?

Ты неправильно понял. Там же написано, что число максимально 2^64-1. Нужно обнулить все младшие биты

Да Вы правильно поняли.

Например, в каком виде подаётся разрядность?

Число произвольное u64. Сдвиги использовать можно

while — условный оператор.

>Сдвиги использовать можно

Тю. Тогда задача не интересна :)

Без условного оператора от сдвигов толку 0.

>Без условного оператора от сдвигов толку 0.

Как это? Зачем условный оператор при наличии сдвигов?

а, млеат, я тут просто первые биты показываю

Зачем условный оператор при наличии сдвигов?

А как вы проверите, что достигнут предел? (см. мой пример)

>Тю. Тогда задача не интересна :)

И какое решение? ;)

>И что, для 64битного числа проканает?)

Если написать return a & (~0xffULL), то должно проканать.

Тю. Тогда задача не интересна :)

А как? Мне пока ничего в голову не приходит, кроме разворота в одно выражение подобного говноцикла:

u64 oldbit=0;
for (i=63;i>=0;i--){
    a&=~oldbit;
    oldbit|=a&((1<<i));
    oldbit>>=1;
}    

Циклы использовать нельзя ;)

У меня пока есть такое решение:

(...((x & (~(x >> 1))) & (~(x >> 2))...&(~(x>>63))

Но оно наверняка неоптимальное

>Циклы использовать нельзя ;)

Так я и написал про разворот того цикла. В итоге это и получится:

(...((x & (~(x >> 1))) & (~(x >> 2))...&(~(x>>63))

>А как? Мне пока ничего в голову не приходит, кроме разворота в одно выражение подобного говноцикла

Его и имел в виду. Некрасиво, но условия выполняет :)

Да, правильно. Я сразу не въехал

можно

x = x - (x >> 1);

Можно, конечно. Но в условии не было минуса.

>Но в условии не было минуса.

Минус эмулируется через базовую логику. Но будет ещё сложнее, чем в варианте с раскрученным циклом :)

А по-моему нельзя.

а вообще

http://aggregate.org/MAGIC/#Most%20Significant%201%20Bit

В общем случае заменять операции таким образом нельзя. Но в данном примере к последней строке x имеет значение ob1111...1, то есть сумма соответствующих степеней двоек. Поэтому использование вычитания из этой суммы всех степеней двоек кроме наибольшей вполне корректно.

Я про то, что
0b010 - 0b001 = 1
Или я чего-то не понял?

Что за странное условие на отсутствие условного перехода? Если мы пишем софт, то у нас в любом случае есть условный переход.

А если мы пишем железо, то число можно представить в виде битового массива, завести 63 каскадных or и поandить... Ну, или, если по скорости оптимизировать, то сделать побольше оров потолще и параллельно их...

В данном случае число x имеет вид 0b111...111. Пусть в нем n единиц. Тогда вычитается из него число, состоящее из (n-1) единиц. То есть 0b1111 - 0b0111 == 0b1000.

А вообще :)

#include <stdint.h>
#include <stdio.h>

unsigned uint64_highest_bit_pos(uint64_t vect)
{
#if (defined (__x86_64__) || defined (__x86_64) || defined (__amd64))
  uint64_t pos = 0;
  asm volatile ( "bsrq %0, %0;"
                    : "=r" (pos)
                    :  "0" (vect) );
  return (unsigned)pos;
#else
  unsigned shift = 32;
  unsigned pos, v32 = (vect >> 32) & 0xffffffff;
  if (!v32) {
    v32   = vect                   & 0xffffffff;
    shift = 0;
  }
  asm volatile ( "bsrl %0, %0;"
                    : "=r" (pos)
                    :  "0" (v32) );
  pos += shift;
  return pos;
#endif
}

int main(int argc, char *argv[])
{
    uint64_t x = atoll(argv[1]);
    if (x) x = 1 << uint64_highest_bit_pos(x);
    printf("%lu\n", x);
}