1. C++ / Говнокод #1590

    +6.9

    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
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    40. 40
    41. 41
    42. 42
    43. 43
    44. 44
    45. 45
    46. 46
    47. 47
    48. 48
    49. 49
    50. 50
    51. 51
    52. 52
    53. 53
    54. 54
    55. 55
    #ifndef SOCHET_H
    #define SOCHET_H
    
    // Сдвигает самую младшую единицу в сторону младшего разряда
    #define shiftLast1Right(x) ( (x-1)^((x^(x-1)) >> 2) )
    
    // Дописывает 1 после самой младшей единицы
    #define add1AfterLast1(x) ( x | ((x^(x-1))+1) >> 2 )
    
    template<class T>
    class Sochet
    {
    public:
    	T value;
    
    	//////////////////////////////////////////////////////////////////////////
    
    	Sochet():value(0) { }
    	Sochet(int n, int k) {
    		firstTurn(n, k);
    	}
    	~Sochet() {
    		value = 0;
    	}
    
    	//////////////////////////////////////////////////////////////////////////
    
    	// Первая комбинация
    	// В первоначальной ситуации все К единиц располагаются в старших битах
    	void firstTurn(int n, int k) {
    		value = ( ( T(1) << k ) - 1 ) << (n - k);
    	}
    
    	// Нахождение следующей комбинации
    	// Возвращает false в случае последней комбинации
    	bool nextTurn()
    	{
    		// Отлов последней комбинации
    		if (value & (value+1) == 0)
    			return false;
    		
    		// Условие по младшему биту: 1 или 0
    		if (value & 1)
    		{
    			value >>= 1;
    			nextTurn();
    			value = add1AfterLast1(value << 1);
    		} else
    			value = shiftLast1Right(value);
    		
    		return true;
    	}
    }
    
    #endif // SOCHET_H

    Шаблон перебора всех сочетаний/выборок в много разрядных числах.
    Пример перебираемых чисел для N=5, K=3:
    11100
    11010
    11001
    10110
    10101
    10011
    01110
    01101
    01011
    00111

    // Код выглядит сочно(особенно дефайны), зато всё работает максимально быстро.
    // Статья про этот алгоритм: http://k06a.blogspot.com/2009/04/blog-post_08.html

    Запостил: k06a, 15 Августа 2009

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

    • Говнокод здесь - дефайны. Сложно понять что делают, зато делают это максимально быстро.

      Если бы я запостил одни дефайны - было бы не понят нахрена они вообще такие нужны.
      Ответить
      • >> Говнокод здесь - дефайны. Сложно понять что делают, зато делают это максимально быстро.

        Комментарии для кого писали, батенька?
        Ответить
    • Сломал хатуманенный алкоголем мозг. Прошу объяснить популярно, в чём хохма.
      Ответить
    • Я обоссался!!! Это же пиздец!!!
      Ответить
    • Позерство детектед!
      Ответить
    • Негодую, не говнокод, раз работает "максимально быстро".
      Ответить
    • Говнокод только в названии класса.
      Ответить
    • Забавно, а если T == float или string?
      Ответить

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