I guess the sense of 'not HALF bed' is there is no even a HINT for anything bad in it. It is idiomatic, somekind like Russian 'без сучка без задоринки' or 'комар носа не подточит'. А теперь представьте, что вас иностранец спросит: "а что такое эта самая задоринка?", вот что вы ему тогда будете рассказывать? Вот так и тут примерно )) Ну а "комар, который нос подточить не может" - вообще из разряда смысловых галлюцинаций, с точки зрения логики )))

Max, I don't know if this expression has an exact definition, but here is how I would use it. That's bad!......That is excellent! That's not bad!.......That is very good! That's not half bad!....That's pretty good, better than I expected. (If it was 100% bad, it would in fact be very, very good.)

I'm not sure of the origins of the phrase but it is a semi-commonly used colloquial expression when you want to compliment someone on the job they have done, or the work they have created, etc. Sometimes it is also used to slightly tease someone. ex- Your sister bakes her first cake. You tell her, "that's not half bad!" A friend has you listen to some music he likes. "that's not half bad!"