1. Си / Говнокод #3454

    +141

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    #include <stdio.h>
    
    int main() {
    	unsigned d,t,k;
    	scanf("%d",&d);
    	t=d;
    	for(k=0;t!=0;k++) //определяем кол-во значащих битов
    		t>>=1;
    	//обнуляем старший значащий бит
    	d<<=sizeof(d)*8-k+1; 
    	d>>=sizeof(d)*8-k+1; 
    	return 0;
    }

    Вот такое вот обнуление старшего бита

    Запостил: movaxbx, 11 Июня 2010

    Комментарии (64) RSS

    • k = 0;
      if (d > 1) {
        while ((d << k) >> k == d) k++;
        d <<= k;
        d >>= k;
      }
      else d = 0;
      Ответить
      • for (k=0;(signed)d>0;k++)
                d<<=1;
            d=d<<1>>(k + 1);
        Ответить
        • for(t = d, k = INT32_MIN; (t == d) && k ; d&=~k, k>>=1);

          или
          k = INT32_MIN;
          while((d == (d&=~k)) && (k>>=1));
          Ответить
    • ужос, какие тут жестокие способы обнуления бита 0_0
      после такиз говнокодов начинаешь задумыватся о удобстве и легкости ассемблера ))
      Ответить
      • А как надо? Ткни носом, плиз...
        UPD: Хотя бы на асме
        Ответить
        • Да хотя бы вот так:
          d&=~(1<<k);
          Ответить
          • Так это ничем не лучше и не хуже
            d <<= k;
            d >>= k;
            Ответить
            • надо смотреть как это преобразует оптимизатор...
              Ответить
        • >>Хотя бы на асме
          пожалуйста 3 строки

          bsr eax,cl
          jz skip ;если eax=0
          btr eax,cl
          skip: ....

          Как говорится
          Use asm Luke

          bsf and bsr instructions scan a word or double word for first set bit and store the index of this bit into destination operand, which must be general register. The bit string being scanned is specified by source operand, it may be either general register or memory. The ZF flag is set if the entire string is zero (no set bits are found); otherwise it is cleared.
          Ответить
          • Красиво, блин...
            Тока там явно не CL.
            Ответить
            • >>Тока там явно не CL.
              ага, это я на автомате как я юзаю в shr написал
              и еще там jz skip по большому счету не сильно нужен
              Ответить
          • Есть ещё "cntlz", AFAIK. ;)

            Хотя признаюсь, сам я данной инструкцией ниразу в жизни не пользовался и может просто не знаю о существовании каких-нибудь "подземных камней", как например со скоростью работы "repe" на современных компьютерах.
            Ответить
        • К сожелению, я видел это только во FreeBSD, но там к такой штуке как ffs() добавили fls(). Я думаю не сложно догадаться по аналогии что оно делает ;)
          Ответить
          • Но подозреваю, что реализованы они тоже не на Си.
            Ответить
          • Это не в BSD, а в gcc. Так называемые intrinsics, которые компилятор сразу заменяет машинным кодом:
            https://gcc.gnu.org/onlinedocs/gcc-4.8.2/gcc/Other-Builtins.html#Other-Builtins
            Ответить
      • время, когда пи был студентом
        Ответить
    • пробегал не раз красивый цикл который итерировал по установленым битам - в отличии от 7-8ой строчек здесь.

      использовался тот факто что если от числа отнять 1 и сделать xor с оригиналом то получится (почти) маска для следующего установленого бита. откусывая от числа нижние установленые биты, в цикле доходится до последнего установленого. и число итераций равно числу установленых битов.
      Ответить
    • В качестве ещё одного варианта говнокода, вместо можно сделать:
      #include <stdio.h>
      
      int main(int argc, char *argv[]) {
              int i,n,t,ot,k,o;
              scanf("%i",&n);
              t=n;
              k=1;
              do {
                      ot=t;
                      t |= t >> k;
                      k<<=1;
              } while(t!=ot);
              t>>=1;
              n&=t;
              printf("%i\n", n);
              return 0;
      }


      Хоть и не многим лучше, но на CeleronM работает ощутимо быстрее.
      Ответить
      • Правда, наверное, было бы намного правильнее развернуть цикл... Тут всего то 5 шагов максимум.

        #include <stdio.h>
        
        int main(int argc, char *argv[]) {
                int n,t;
                scanf("%i",&n);
                t=n;
                t|=t>>1;
                t|=t>>2;
                t|=t>>4;
                t|=t>>8;
                t|=t>>16;
                t>>=1;
                n&=t;
                printf("%i\n", n);
                return 0;
        }
        Ответить
        • Можно записать в одну строчку:
          d&=(t|=(t|=(t|=(t|=(t|=t>>1)>>2)>>4)>>8)>>16)>>1;


          или в 2 строчки:
          for (k=1;t!=(t|=t>>k);k<<=1);
          d&=t>>1;
          Ответить
    • Где-то я видел код обнуления старшего единичного бита совсем без цикла.
      Ответить
      • Жесткий матан =:P

        #include <stdio.h>
        
        int main(int argc, char **argv)
        {
          int float_order_le = 1;
          unsigned long d;
          union { unsigned int u[2]; double d; } t;
        
          scanf("%lu", &d);
        
          t.u[float_order_le] = 0x43300000;
          t.u[!float_order_le] = d;
          t.d -= 4503599627370496.0;
        
          d^=1<<((t.u[float_order_le] >> 20) - 0x3FF);
        
          printf("%lu\n", d);
        
          return 0;
        }
        Ответить
        • Гениально! Я не программист, поэтому возможно просто не знаю какой-то общеизвестной литературы, но нахожу это гениальным.

          Откуда это? Или это собственный алгоритм?
          Ответить
          • Не, мопед не мой:))) Упаси господи!
            http://graphics.stanford.edu/~seander/bithacks.html
            Ответить
            • Спасибо :)

              P.S.: Я смотрю, там немало очень интересных приёмов.
              Ответить
              • Один лишь hasvalue() даст возможность ускорить мои клоны некоторых libc-шных функций в разы! Можно будет провести новые тесты на тему эффективности оригинальных вариантов данных функций.
                Ответить
                • Хотя я переоценил. Дай Бог, если оно проценты даст. Но, всё-равно, приём интересный.
                  Ответить
          • > Я не программист
            – с одной стороны, мы тут все не программисты, а, с другой, хули ты тут забыл тогда?
            Ответить
            • Я и сам, в каком-то смысле, программист
              Ответить
        • Как это, блин, работает?
          Ответить
          • Ну, если коротко, то формат дабла по IEEE754 — 1, 11, 52.
            Первое магическое число — это смещенная экспонента 52 (2**(11-1)-1+52)=1075=0x433

            Второе магическое число — это 2**52 в формате дабла, можно написать как (double)(1LL<<52), тогда не так страшно.

            При таком способе, как мы положили число в дабл, оно все равно что получило старший бит (мы его по стандарту не пишем, потому что в нормализованном виде старший бит всегда равен единице), мы его вычитаем (2**52), и вуаля, оно нормализуется. Сдвигаем экспоненту на 20 бит (чтобы она встала на место в старшем слове). Последнее вычитание — это достать экспоненту из смещенной.

            Как-то так:)
            Ответить
        • Не. Это не так красиво. Сильно много хаков. :) Я где-то видел похожий метод, но лишь в целых числах, через логические и арифметические операции.
          Ответить
          • Есть еще чисто математическое решение с помощью логарифма по основанию 2, но его практическая ценность весьма сомнительна:
            n & ~(2**floor(log2(n)))
            Ответить
            • Логарифм обычно реализуется с использованием цикла.
              Ответить
              • > его практическая ценность весьма сомнительна

                Я привел лишь еще один вариант решения, применять на практике которое я не призывал )
                Ответить
        • union{
              double d;
              unsigned int u[2];
          }t1={.u[1] = 0x43300000}, t2 = {.u[0] = 0};
          
          int main(int argc, char **argv)
          {
            unsigned int d;
            
            scanf("%u", &d);
          
              t1.u[0] = d;
              t1.d -= 4503599627370496.0;
              t2.u[1] = t1.u[1] & 0xfff00000;
              t1.d -= t2.d - 4503599627370496.0;
              d = t1.u[0];
          
            printf("%u\n", d);
          
            return 0;
          }
          Ответить
        • 14 лет назад ещё никакого nil не было
          Ответить
          • В смысле?

            Нил был в лиспе, когда твои родители еще не родились.
            Из лиспа он перекочевал в смалток и в паскаль
            Из смалтока и лиспа в руби
            Из смалкота в ObjC
            из ObjC в Swift

            Впринципе, любое Null-говно есть только в Си и его наследниках.
            Скорее всего это из симулы пошло, но я не уверен

            нил круче нула
            киля азиров не даст соврать
            Ответить
            • Я знаю человека, которого зовут Нил Нилович.
              Ответить
        • какой вконтакте ))
          Ответить
        • Тут нужно не unsigned int, а uint32_t, ибо размер double фикстрованный (64 бита) и не зависит от разрядности процессора, а вот размер int зависит.
          Ответить
          • Размер int зависит не от разрядности процессора, а скорее от желания автора компиялтора (которое может быть конечно продиктовано разрядностью процессора, но не всегда)

            Начиная с c99 пока не возникало необходимости использовать int (кроме конечно случаев когда он явно указан в сигнатуре функции)
            Ответить
            • Верно. Бывают компиляторы под одну платформу с разным размером инта.
              Ответить
              • А кстати, define "разрядность процессора"?

                Бывает размер рабочих регистров, максимальный размер ближнего указателя (в случае сегментной адресации), разрядность шины памяти в конце концов (это важно для выравнивания)
                Ответить
                • Да, кстати, тоже всегда хочу спросить: «А что у него n-разрядное?»

                  У 8088/8086 регистры общего назначения были 16-битными, однако, были инструкции, работающие с 8 битами (половинки типа AH и AL) и с 32 битами (когда аргумент или результат в паре регистров DX+AX), длинные указатели были 32 битными, однако линейный адрес в памяти был 20-битным, а вот размер адреса порта был 10-битным. А у математического сопроцессора регистры были 80-битными, однако, их можно было использовать как 64- и 32-битные.
                  Ответить
                  • В интеле мы обычно имеем ввиду условно говоря размер регистра "AX":

                    AX -- 16
                    EAX -- 32
                    RAX -- 64

                    (причем под словом "полностью 32-х разрядная ОС" в моем детстве например понимали "ОС с поддержкой пейнджинга" -- то-есть ос, требующая 386)

                    Но как это мапится на другие процессоры?
                    Ответить
                    • Это непростая тема. У микрокалькуляторов, например, аппаратные ячейки 4-битные. Однако, микрокод собирает из них виртуальные регистры размером от 48 бит (т. е. микрокод делает из процессора аналог математического сопроцессора). Что считать разрядностью?
                      Ответить
                      • Мне кажется, не нужно нести терминологию Intel на другие процессоры.

                        Утверждать, что процессоры бывают "32-х битные и 64-х битные" потому, что так бывало у Intel, это как утверждать, что языки программирования бывают "вторые" и "третьи" (потому что так было у пайтона)
                        Ответить
                        • Интегралы бывают одинарные, бывают двойные, бывают тройные, а бывает, придёшь домой, а там печь не топлена, дети не кормлены, корова не доена.
                          Ответить
      • union{
            long double ld; // 80 bits
            unsigned int ui[3];
            unsigned long long ull;
        }u1={.ui[1] = 0x80000000,.ui[2] = 0x0000403E}, u2 = {.ui[0] = 0x00000000,.ui[1] = 0x80000000};
        
        int main(int argc, char *argv[])
        {
            unsigned int d; // 32 bits
        
            scanf("%d",&d);
            
            printf("%u\n%x\n%La\n", d, d, u1.ld);
            printf("%08x%08x%08x\n\n", u1.ui[2], u1.ui[1], u1.ui[0]);
           
            u1.ui[0] = d;
            u1.ld -= 0x1p63; // 0x1p63 == 1 * 2^63 == 9223372036854775808ull
            u2.ui[2] = u1.ui[2];
            u1.ld -= u2.ld;
            u1.ld += 0x1p63;
            d = u1.ui[0];
        
            printf("%u\n%x\n%La\n", d, d, u1.ld);
            printf("%08x%08x%08x\n", u1.ui[2], u1.ui[1], u1.ui[0]);
        
            return 0;
        }
        Ответить
        • union{
              long double ld; // 80 bits
              unsigned int ui[3];
              unsigned long long ull;
          }u1={.ui[1] = 0x80000000,.ui[2] = 0x0000403E}, u2 = {.ui[0] = 0x00000000,.ui[1] = 0x80000000};
          
          int main(int argc, char *argv[])
          {
              unsigned long long d; // 64 bits
          
              scanf("%llu",&d);;
              
              printf("%llu\n%llx\n%La\n", d, d, u1.ld);
              printf("%08x%08x%08x\n\n", u1.ui[2], u1.ui[1], u1.ui[0]);
              
              if ((long long)d < 0ll)
              {
                  d&=0x7fffffffffffffffull;
              }
              
              else //*
              {
                  u1.ull = d;
                  u1.ui[1] |= 0x80000000;
                  u1.ld -= 0x1p63; // 0x1p63 == 1 * 2^63 == 9223372036854775808ull
                  u2.ui[2] = u1.ui[2];
                  u1.ld -= u2.ld;
                  u1.ld += 0x1p63;
                  u1.ui[1] &= 0x7fffffff;
                  d = u1.ull;
              }
              
              /*/ // или
              {
                  u1.ull = d | 0x8000000000000000ull;
                  u1.ld -= 0x1p63; // 0x1p63 == 1 * 2^63 == 9223372036854775808ull
                  u2.ui[2] = u1.ui[2];
                  u1.ld -= u2.ld;
                  u1.ld += 0x1p63;
                  d = u1.ull & 0x7fffffffffffffffull;
              } // */
          
                  
              printf("%llu\n%llx\n%La\n", d, d, u1.ld);
              printf("%08x%08x%08x\n", u1.ui[2], u1.ui[1], u1.ui[0]);
          
              return 0;
          }
          Ответить
    • интересно, чем не устроило
      d=d<<1>>1;
      ?
      Ответить
    • The lowest-power machine configuration the Windows 95 team
      had in mind was an Intel 386SX-based system with 4 MB of memory, a
      VGA display, and 80 MB of disk space.
      Ответить
    • Amazingly, one of the "techniques" used by some existing
      Windows applications relies on allocated resources remaining available
      even after the application quits. For this reason, the resource cleanup
      can't take place until the system notices that there are no 16-bit applications running.

      Какой ротоёб'92
      Ответить
      • Когда в сеть утекла часть исходников Windows, оказалось, что в MS в новые версии Винды добавляли патчи, чтобы ротоёбские приложения, завязанные на странную хуйню из старых версий, продолжали работать. А когда это недоразумение из Винды вычищали, поднимался вой на болотах.
        Ответить
        • так это

          compatibility toolkit же
          Ответить
          • Вот тут несколько забавных комментариев к коду:

            https://govnokod.xyz/_11319/#comment-388889
            Ответить

    Добавить комментарий