вторник, 2 ноября 2010 г.

Try to f(f(n)) == -n

Увидел недавно интересный вопрос.
Написать такую функцию f, что: f(f(n)) == -n

У кого какие идеи?

Вот самый простой вариант на мой взгляд (правда это не совсем функция):
#define f(n) 0-n
Ну а вот посложнее (правда тут получается 2 функции с одним именем):

template<typename T>
struct param
{
   T n;
   param(T t) : n(t) {}
};

template<typename T>
param<T> f(T n)
{
   T a = (1&(n^(n>>1)));
   n ^= (a ? 0xAA : 0x55);
   return param<T>(n);
}

template<typename T>
T f(param<T> n)
{
   return f(n.n).n + 1;
}

(ссылка - http://codepad.org/TK0GhhAe)

Этот код пока работает только для char.
Так было намного быстрее прогонять полный тест))
Нетрудно модифицировать его для остальных типов.


Читать дальше

Printf структуры?

Угадайте с трёх раз, что выведет следующий код, скомпилированный VS2008?

struct A
{
   int a;
   int b;
   int c;
};

A a = { 10, 20, 30 };

printf("%d %d %d\n", a);


Да, именно то самое: "10 20 30".
И вообще нет никакой проверки типов,
а следовательно и неявного кастования.
Кто, что думает по этому поводу?

Вот что думают на StackOverflow: http://stackoverflow.com/questions/4081491

Читать дальше

воскресенье, 24 октября 2010 г.

Создал новый проект на Google Code - boolib

Наконец-то добрались руки создать проект персональной C++ библиотеки. Буду туда закидывать все решения, которые можно будет многократно использовать. Классы, шаблоны и всё что получится.

Для начала создал инструмент synchronize(id) для синхронизации потоков в стиле Java. В защищённый блок с одним идентификатором одновременно сможет попасть лишь один поток. Использовать так:


// ...

synchronize(153)
{
   // защищённый код
}

// ...


Сегодня узнал, что POSIX Threads под Windows нужно скачивать ОТДЕЛЬНО!
Почему его нет в Visual Studio по-умолчанию? Это же POSIX!
В общем, synchronize(id) работает только под Windows (использует Mutex-ы).

Читать дальше

вторник, 19 октября 2010 г.

6 последовательных проблем программиста

6 последовательных проблем программиста:
1) Как бы написать, чтобы скомпилировалось?
2) Как бы написать, чтобы работало как задумано?
3) Как бы написать, чтобы работало быстрее?
4) Как бы быстрее написать?
5) Как бы написать, чтобы было красиво?
6) Как бы написать, чтобы было гибко и повторно-используемо?

Читать дальше

пятница, 20 августа 2010 г.

Исповедь нулевого указателя (Apology of the NULL pointer)

Перевод статьи Apology of the NULL pointer.

"Никто не любит меня. Меня презирали везде, где я побывал. Меня обвиняют в большинстве проблем, а иногда даже в некоторых катастрофах. Некоторые говорят, что я проклят. Некоторые утверждают, что я какая-то болезнь, которую необходимо вылечить. Когда люди видят меня, первая их мысль: "О нет, только не это ...". Ни у кого не найдется доброго слова для меня. Люди готовы тратить часы за часами, чтобы убедиться в том, что меня нет поблизости. Они проводят невероятно много времени выискивая пути, для обхода меня, чтобы раздавить меня, и убедиться в том, что я не могу даже приблизиться к ним. Дальше только хуже, некоторым людям удалось сделать меня невидимым для своих глаз, так что даже если я появляюсь они не видят меня. Если мне удастся приблизиться и сказать "привет", люди не отвечают "привет" мне. Когда я что-либо говорю, люди смотрят на меня с отвращением. Люди издавна считают, что я самое худшее, что может случиться с их программным обеспечением.
Они просто не понимают меня. На самом деле я думаю, что меня вообще НИКТО не понимает. Но это нормально, потому что не важно буду ли я рядом, когда вы выпускаете ваше программное обеспечение. Я все равно буду рядом, когда ваше программное обеспечение устареет. В действительности, вы можете рассчитывать на то что я рядом всё время. И все же я не преследую вас. Если вы только остановитесь на некоторое время и выслушаете мои слова, вы увидите, что я могу стать вашим лучшим другом. Моя задача очень проста: если я появляюсь в вашем программном обеспечении, это не является признаком того, что ваше программное обеспечение плохо спланировано, я лишь указываю на аспекты не рассмотренные ранее. Если бы вы только поняли, что иногда лучше, чтобы я пришел и сказал вам "привет", чем вы бы хлопнули дверью перед моим лицом. Вы бы поняли, что мы можем работать вместе, чтобы сделать ваше программное обеспечение лучшим когда-либо существовавшим программным обеспечением. Так что, пожалуйста, прекратите проклинать меня и на этот раз постарайтесь прислушаться к моему посланию."

На текст выше был я вдохновлен разговором с коллегами о том, в каких случаях следует выявлять нулевые указатели, а в каких просто позволить программе упасть.

Оригинал статьи.
Читать дальше

пятница, 9 июля 2010 г.

Задачки

Написал более или менее внятные объяснения задачек на квизфуле:
1) Задачка про поиск уникального значения (ссылка) (копия)
2) Задачка про сумму и произведение чисел (ссылка) (копия)

Читать дальше

воскресенье, 4 июля 2010 г.

Шаблонная реализация перевода числа в строку

Шаблонная реализация функции перевода числа в строку.
Практического толку не очень много, зато разобрался в шаблонах получше.

Логарифм произвольного основания:



Сам перевод в строку:



Вам предлагается найти ошибки. Одна точно есть и допущена специально.

Вот исходный код: http://codepad.org/YeanrJjQ

UPD:
Чуток изменил код, ошибку исправил тоже.
Теперь используется статическая память, вместо динамической.



Теперь посмотри как Visual Studio 2008 разберётся с этим:



Вот что у нас получилось:



Видно как в статическую память записываются 3 цифры '7',
'3', '1' и производится вызов функции печати на консоль.

Код для Visual Studio тут - http://codepad.org/Z4rplbF7
Для других компиляторов следует закомментить лэйблы со смайлами)))


Читать дальше

воскресенье, 4 апреля 2010 г.

Делюсь ресурсами

1. Cheat-Sheets.org - Замечательный сайт IT шпаргалок. Содержит шпоры по огромному числу языков программирования, технологий и прочему.

2. Wotsit.org - Сайт с множеством описаний различных форматов файлов. Частенько использую для получения неофициальной информации по форматам.

3. Koders.com - База данных исходных кодов на разных языках. Указаны типы лицензий.

Продолжение следует . . .
Читать дальше

Почему пишут ++i вместо i++. Простейшее объяснение.

Наиболее простое описание, почему иногда лучше использовать ++i нежели i++. Я просто приведу пример с перегрузкой префиксного(++i) и постфиксного(i++) операторов в неком классе Alpha.
class Alpha
{
public:
Aplha & operator++ (); // префиксная форма (++alpha)
Alpha operator++ (int); // постфиксная форма (alpha++)
};
Отличие сразу бросается в глаза. Теперь, если вы знаете что такое &, то вам понятно какой из операторов быстрее отработает в случае большого sizeof(Aplha).

Но наиболее важной частью сего поста я считаю данную ссылку:
1. C++ FAQ Lite: C++ FAQ Lite
2. Конкретно про i++ и ++i: C++ FAQ Lite 13.14
Читать дальше

суббота, 3 апреля 2010 г.

Top 25 программистских шуток про Чака Норриса

Перевод сообщения "The Ultimate Top 25 Chuck Norris «The Programmer» Jokes" из блога {сodesqueeze} (копия):

1. Когда Чак Норрис выбрасывает исключение, оно пролетает через всю комнату.

2. Все массивы, объявляемые Чаком Норрисом имеют бесконечный размер, потому что Чак Норрис не знает границ.

3. Для Чака Норриса не существует задержки диска, потому что диск чертовски торопится.

4. Чак Норрис пишет код, который оптимизирует сам себя.

5. Чак Норрис не может проверять на равенство, потому что он не имеет равных.

6-а. Чаку Норрису не требуется сборщик мусора, потому что он не использует .Dispose(), он вызывает .DropKick().

6-б. Чаку Норрису не требуется сборщик мусора, потому что он не высвобождает память, а лупит по ней ногой с разворота.

7. Первая программа Чака Норриса была kill -9. (Прим.пер. описание kill -9)

8. Чак Норрис лопнул пузырь доткомов. (Прим.пер. Dotcom Bubble)

9. Все браузеры поддерживают шестнадцатеричные константы #chuck и #norris для чёрного и голубого цветов.

10. MySpace на самом деле не ваше пространство, оно Чака - он лишь позволяет вам использоваться им.

11. Чак Норрис может написать бесконечную рекурсивную функцию ... и заставить её завершиться.

12. Чак Норрис может решить Башни Ханоя в один ход.

13. Единственный паттерн проектирования известный Чаку Норрису - Божественный объект. (Прим.пер. God Object)

14. Чак Норрис прошёл World of Warcraft.

15. Руководители проекта, не пытайтесь оценивать Чака Норриса ... никогда.

16. Чак Норрис не пишет в соответствии с веб-стандартами, так как веб всегда будет соответствовать ему.

17. "Она работает на моей машине" всегда справедливо для Чака Норриса.

18. "Маркерные доски" имеют белый цвет, потому что белеют от ужаса перед Чаком Норрисом. (Прим.пер. Whiteboard)

19. Чак Норрис не использует схем Burn Down, он предпочитает таблицы Smack Down. (Прим.пер. Burn down chart + Smack Down)

20. Чак Норрис может удалить корзину.

21. Борода Чака Норриса может печатать 140 символов в минуту.

22. Чак Норрис может проводить модульное тестирование всего приложения с одним единственным assert-ом.

23. Чак Норрис не ведёт охотиту за багами, потому что слово "охота" допускает возможность неудачи. Чак предпочитает убивать баги.

24. Клавиатура Чака Норриса не имеет клавиши Ctrl, потому что никто и ничто не контролирует Чака.

25. Когда Чак Норрис занимается веб-серфингом веб-сайты отображают сообщение "Предупреждение: Internet Explorer счел этого пользователя вредоносным или опасным. Вы действительно хотите продолжить?".

Знаете другие? Комментируйте ...

Читать дальше

четверг, 1 апреля 2010 г.

Задачка про уникальность

1. Имеется массив чисел конечной длины. Все числа в нём присутствуют ровно в двух экземплярах. И лишь одно число присутствует в единственном экземпляре. Необходимо за минимальное(конечное) число проходов по массиву определить значение этого уникального числа.

2. Решить ту же задачу, только теперь имеется два уникальных числа.

(Задачку позаимствовал у Смола)

UPD: Александр, на память ограничения не накладываются. Желательно использовать разумное количество памяти. Может получиться, например, прямая зависимость между используемой памятью и сложностью алгоритма(число операций), тогда это стоит отдельно обговорить в ответе.

UPD_2: Для поиска одного из чисел используется операция XOR для всех элементов массива. В результате пары элементов дадут нули, а уникальное число останется в результате.

Для поиска 2-х числе необходимо использовать следующий алгоритм:

При первом проходе считать 2 различных XOR-а, в один складывать числа большие 0x80000000, а в другой - меньшие.

Если обе XOR-суммы не равны нулю, то оба XOR-а равны соответствующим уникальным числам.

Если один из XOR-ов равен нулю, то диапазон на котором XOR не равен нулю снова делится пополам.

В результате число проходов пропорционально логарифму разрядности чисел, то есть O(log2(sizeof(n))).

Читать дальше

четверг, 11 марта 2010 г.

Multithreaded std::cout.

Постоянно встречался с тем, что конструкция типа:
std::cout << "123" << a << "456" << b << std::endl;
работает не очень хорошо из нескольких тредов(потоков) одновременно.
Каждый такой оператор "<<" представляет из себя отдельный вызов функции и может вполне случиться, что выводимые данные из разных потоков перемешаются.

Придумал небольшой трюк для устранения этой проблемы.
Теперь вместо #include <iostream> подключаю свой #include "mt_iostream".

Содержимое mt_iostream:
#include <iostream>
#include <sstream>

namespace std
{
class mt_ostream : public ostringstream
{
public:
mt_ostream() : ostringstream() {}
~mt_ostream()
{
cout << str();
}
};
} // namespace std

#define cout (static_cast<mt_ostream&>mt_ostream())

Подсветка синтаксиса выполнена при помощи Notepad++




И в качестве бонуса, небольшой trick для получения различных последовательностей rand() в разных тредах (обычно они совпадают). В начале работы каждого из тредов вызывайте функцию srand, передавая ей параметром текущее время. Это вы знали и без меня, это не помогает. Вот этот макрос поправит ситуацию:
#define srand(x) srand(x + GetCurrentThreadId())

Читать дальше

вторник, 2 марта 2010 г.

понедельник, 22 февраля 2010 г.

torrents.ru => rutracker.org

=>

Прописал у себя в файле hosts (зеркало страницы):
195.82.146.114 torrents.ru
195.82.146.120 bt.torrents.ru
195.62.63.163 bt1.torrents.ru
195.82.146.121 bt2.torrents.ru
195.62.62.241 bt3.torrents.ru
195.82.146.123 bt4.torrents.ru
Теперь живу как и раньше))

Местоположение файла hosts:

Windows 95/98/ME: WINDOWS\hosts
Windows NT/2000: WINNT\system32\drivers\etc\hosts
Windows XP/2003/Vista/7: WINDOWS\system32\drivers\etc\hosts
Читать дальше

суббота, 20 февраля 2010 г.

Поговорим об SMS Protocol Data Unit

Решил поближе познакомиться с форматом SMS сообщений. Далее я напишу несколько закономерностей/законов, которые помогут мне написать достойную библиотеку c виртуозной архитектурой для работы с SMS PDU. Только учтя все особенности формата, возможно создать в меру сбалансированную библиотеку. Под балансировкой я понимаю выбор достаточного числа классов, структур, перечислений, способов взаимодействия компонентов между собой и интерфейса для использования библиотеки.


В статье используются сокращения:
SME - Short Message Entity (Модуль мобильного устройства)
SMSC - SMS-Centre (Центр обработки сообщений)
PDU - Protocol Data Unit (Протокольная единица данных)

В первую очередь примечательно, что имеется 6 типов сообщений:
+ SMS-SUBMIT
+ SMS-SUBMIT-REPORT
+ SMS-DELIVER
+ SMS-DELIVER-REPORT
+ SMS-STATUS-REPORT
+ SMS-COMMAND (посылка специальных команд от SME к SMSC)

Использование первых пяти типов поясняет эта схема:
SMS PDU Types

Тип сообщения хранится в 2-х битах первого байта. Неправда ли, маловато 2-х битов для хранения 6 возможных значений? Конечно мало, но если вы знаете кто это сообщение сгенерировал, то вам остаётся прочитать из 2-х бит всего 3 возможных значения.

Типы сообщений от SME:
( 0 1 ) SMS-SUBMIT
( 0 0 ) SMS-DELIVER-REPORT
( 1 0 ) SMS-COMMAND

Типы сообщений от SMSC:
( 0 1 ) SMS-SUBMIT-REPORT
( 0 0 ) SMS-DELIVER
( 1 0 ) SMS-STATUS-REPORT

Первый байт всегда содержит флаги/индикаторы. Все данные пакета измеряются в байтах, некоторые переменной длинны. То, какие флаги присутствуют в пакете - определяется типом сообщения. Присутствующие поля определяются типом пакета и флагами.

Принципы планируемой библиотеки:
1) Каждому типу сообщения - свой класс, наследованный от базового. Каждый из них будет иметь свои флаги/индикаторы и обязательные поля. Некоторые флаги/индикаторы будут реализовываться отдельными классами, и будут иметь указатели на классы связанных с ними полей. Базовый класс будет уметь определять тип сообщения и создавать экземпляр соответствующего класса. [Напрашивается применение предыдущего поста про "кастование от родителя к наследнику"]
2) Классы храня данные только в самом PDU. (никаких промежуточных полей)
3) Каждое из полей наследуется от универсального класса "единицы данных". Имеет встроенные методы, по изменению размера и поля и перемещению данных в памяти. Обладает указателем на следующую "единицу данных", при изменении своего размера, заставляет двигаться следующую за ним "единицу данных".
4) [В разработке]


Читать дальше

пятница, 19 февраля 2010 г.

Кастование от родителя к наследнику

Класс наследуется от некого базового класса-шаблона, передавая своё имя в качестве параметра шаблону. Базовый класс имеет метод, статически кастующий указатель на экземпляр конкретного класса к шаблонному типу. Таким образом возможно удобное статическое кастование от родителя к наследнику. И как следсвие, вызов переопределённых в наследнике методов из базового класса без их виртуализации. (вольное описание приёма из библиотеки sl)

Приблизительный код:
////////////////////////////////////////////////////////////////

template <typename T>
class SelferT
{
public:

T &GetSelf()
{
return static_cast<T &>(*this);
}

const T &GetSelf() const
{
return static_cast<const T &>(*this);
}

};

////////////////////////////////////////////////////////////////

class RefCount : protected SelferT<T>
{
public:

// Конструктор копирования - увеличивает счётчик ссылок
RefCount(
IN const RefCount &rhs
) : _refCount(rhs._refCount)
{
// ...
}

// Оператор присваивания - увеличивает счётчик ссылок
RefCount &operator=(IN const RefCounted &rhs)
{
// ...
}

// Деструктор - уменьшает счётчик ссылок
~RefCount()
{
// ...

if (*_counter == 0)
GetSelt().OnDispose();
}

// Вызывается, когда число ссылок становится равно нулю
void OnDisposed()
{
}

};

////////////////////////////////////////////////////////////////

class A : public RefCount<A>
{
public:

// ...

// Вызывается, когда число ссылок становится равно нулю
void OnDisposed()
{
}

};

////////////////////////////////////////////////////////////////

Подсветка синтаксиса выполнена при помощи Notepad++




Если виртуализация методов класса позволяет добраться до последнего наследника базового класса, то данный метод позволяет добраться до конкретного наследника. С этим приёмом мы получили интерфейс в стиле Java, но без обязательного переопределения методов.

Ссылка по теме:
Преобразование ссылки на интерфейс для реализации класса в Delphi 2010

Читать дальше

понедельник, 4 января 2010 г.

Прикрутил Spoiler

Прикрутил к блогу спойлер by Ruby Brewed (Denis Neverov http://dotrb.blogspot.com)
Он будет весьма востребован в готовящейся в данный момент статье.



А здесь текст, который хотим сделать скрытым


Читать дальше