Posts tagged c

Swap the value of two integers without temporary storage

Jan 13th

Posted by Detro in Personal

2 comments

Someone says this is an old lame trick. I think it’s simple and clever use of XOR.

How/Why does it work?

It’s built around the properties of the XOR ^ operator, who has the following properties:

  • A ^ B = B ^ A (commutative)
  • A ^ 0 = A
  • A ^ 1 = ~A
  • A ^ A = 0

So, you can see how it get’s applied here:

#include <stdio .h>
int main(void)
{
   unsigned int a, b;
   // ... populate somehow "a" and "b"...

   printf("a = %d - b = %d\n", a, b);

   a ^= b; // store in "a" the value of "a XOR b"
   b ^= a; // store in "b" the value of "a XOR b XOR b" = "a XOR 0" = "a"
   a ^= b; // store in "a" the velue of "a XOR b XOR a" = "b XOR 0" = "b"

   printf("a = %d - b = %d\n", a, b);
}

Neat.

, , , , , , , ,

Count bits set in parallel

Jan 7th

Posted by Detro in IT / Comp-Sci / Code

2 comments

This time it’s not something I make myself. Indeed, I still can’t “see” it 100%: I got it, but it’s a bit complex.

Counting kid
A cute little lady counting (bits? ;-) )

It’s a method to count the number of bits in a number in O(1), in just 5 lines of code. INHUMAN.

The “human” solutions

Of course, there are methods that look way more easy and, given that the size of a number in memory is “fixed”, the O(1) still stands. For example:
0. Based on the “evenness/oddness” of the number

unsigned int bits_counter_v0(unsigned int x) {
    unsigned int count = 0;
    while ( x != 0 ) {
        // If odd, add 1
        count += (x % 2 == 0) ? 0 : 1;
        x >>= 1;
    }

    return count;
}

1. Counting one bit at a time (always the least significant one)

unsigned int bits_counter_v1(unsigned int x) {
    unsigned int count = 0;
    while ( x != 0 ) {
        // If least-significant bit is 1, add 1
        count += (x & 1) ? 1 : 0;
        x >>= 1;
    }

    return count;
}

2. Counting 4 bit at a time with max 8 shifts, using an “hashmap” with precalculated results
The fact that it can count the bits in “max 8 shifts” has the trade off of the memory used by the hashmap.

unsigned int bits_counter_v2(unsigned int x) {
    unsigned int count = 0;
    // "Hashmap" of the values for the least significant 4 bits
    unsigned int int_to_bits_count[16] = {
        0, // 0  00
        1, // 1  01
        1, // 2  10
        2, // 3  11
        1, // 4  100
        2, // 5  101
        2, // 6  110
        3, // 7  111
        1, // 8  1000
        2, // 9  1001
        2, // 10 1010
        3, // 11 1011
        2, // 12 1100
        3, // 13 1101
        3, // 14 1110
        4  // 15 1111
    };

    while ( x != 0 ) {
        // Add the bits count of the least significant 4 bits
        count += int_to_bits_count[ x & 15 ];
        x >>= 4;
    }

    return count;
}

Let’s see what some insane people made. More >

, , , , , , ,

Find the non repeating char in O(n) time and O(1) space – v2

Dec 18th

Posted by Detro in Personal

4 comments

My colleague and friend Luca (@lucabox) described a better solution to the problem of “Finding the first non repearing char in a string in O(n) time and O(1) space“. It uses smartly the space, making the solution nicer and slicker.
Or we are just 2 geeks that need to give more attention to their girlfriends :P

Luca’s solution description

The logic of this solution is based on the usage of an array of unsigned chars.
Every char (assumed to be lowecase) has an associated small byte (1 char = 8 bits), where the bits 0×1 and 0×2 (the 2 least significant) represents, respectively, “present once in the input string” and “present multiple times in the input string“. After the input is “scanned” once, and every letter is marked with the correspondent “presence bit” (once, multiple or none), it get’s scanned a second time to find the first char of the input which has the bit “present once” set to “1″.

Before I show you the code

Again, this comes from Luca Colantonio (http://uk.linkedin.com/in/lucacolantonio), smart ass that is too lazy to maintain a blog and post it himself (or even implementing himself – he just explained to me at work and I had to code it). Thanks Luca ;)

Now, the code.
More >

, , , , , , , , , , ,

Il VERO fattore WOW!!!

Jan 31st

Posted by Detro in Curiosity

No comments

Pollycoke, che sta ormai acquistando una certa notorietà in tutta la comunità Italiana (ma non solo), ci parla di una proposta SCONVOLGENTE (in positivo) fatta dalla comunità degli sviluppatori del Kernel ai produttori di hardware:

[…] the Linux kernel community is offering all companies free Linux driver developmentAll that is needed is some kind of specification that describes how your device works, or the email address of an engineer that is willing to answer questions every once in a while. […] In return, you will receive a complete and working Linux driver that is added to the main Linux kernel source tree

Inutile che mi dilunghi, lui ha già scritto abbastanza e in maniera esauriente. Vi rimando al suo blog.

, , , , , ,

XGL: OpenGL sempre più prepotentemente sui nostri Desktop

Feb 11th

Posted by Detro in IT / Comp-Sci / Code

10 comments

XGL: tutti ne stanno parlando ultimamente. Ci sono articoli in ogni dove su XGL ma… che é?
Prendiamo da Wikipedia:

Xgl is an X server architecture, started by David Reveman, layered on top of OpenGL via glitz. Some say that it is seen as the future of the X.Org Server, but some disagree because it requires a 3D graphics card. Although most PCs are nowadays shipped with such a card, most vendors (most notably NVIDIA and ATI Technologies) don’t provide open source drivers for their cards, which do not work on all computer architectures supported by the X.Org Server.

As of January 2006, it is still at an early stage in development and a number of important pieces are still missing, but progressed well in 2005. Its source was opened up on January 2, 2006 [1] [2], and included in freedesktop.org, along with major restructuring to allow wider range of supported display drivers. X server backends used by Xgl include Xglx and Xegl. In February 2006 the server gained wide publicity after a public display where the Novell desktop team could demonstrate a desktop with much eye-candy such as translucent windows and a rotating 3D desktop. The eye-candy effects are implemented in a compositing window manager called Compiz [3].


Quindi, per farla breve, questo XGL é una implementazione di XServer (che trova la sua prima embrionale realizzazione in Xglx) e che si basa, per ora, sull’uso di X.Org come backend preesistente. Novell ha sviluppato, in concomitanza, un nuovo Window Manager/Compositing Manager chiamato Compiz che potrebbe (il condizionale é d’obbligo) entrare a far parte del progetto Gnome e, forse/addirittura, soppiantare Metacity. Il condizionale é d’obbligo perché:

  1. Non voglio essere linciato da chi ne capisce più di me in questo campo
  2. Le notizie sono ancora confuse, dato che poca gente ha già messo piede sul CVS ufficiale rilasciato da Novell
  3. Non ho tempo per mettermi con le mani nel codice personalmente
  4. Si tratta di un progetto alla versione 0.0.1 e come tale poco più che un agglomerato di API

Inoltre, esiste un progetto a mio parere ben più interessante sul lungo termine:

Xegl is the future of Xgl and the long term goal of X server development. Xegl is a server that implements the EGL API and uses Mesa-solo to provide OpenGL rendering directly to the Linux framebuffer. As of August 2005 Xegl can only be run using Radeon R200 graphics hardware and development has currently been delayed… (continua su Wikipedia)

A quanto pare il consorzio/organizzazione OpenGL si é spremuta le meningi per sviluppare uno standard, EGL appunto, su cui basare lo sviluppo di tutti i futuri Desktop-Environment, partendo dalla base stessa: il Server Grafico.

Come molti utenti, anche io storco un attimino il naso: se non disporrò di una scheda grafica 3D, presto mi ritroverò a non poter usare nulla dei nuovi programmi che verranno sviluppati per il Desktop Linux. Ma il mio storcere il naso é maggiormente rivolto a tutti quei produttori che, per un motivo o per un altro, ancora non vedono il Pinguino come un mercato per cui sviluppare driver. E sarei anche disposto ad usare un driver chiuso (come quello di Nvidia).

Ma cos’é quindi quello che sta facendo maggior scalpore tra gli utenti?
Bhé, che domande: i video no? Ne sono usciti di demo (uno l’ho appena scaricato e appena finisco di scrivere me lo vado a gustare) e devo dire che di promesse ce ne sono tante.

C’é però da sottolineare una cosa importante: TUTTI cercano di emulare o espandere i concetti che Apple propone RIGHT NOW ai suoi utenti. Ma, si deve anche aggiungere, ho visto cose davvero interessanti, come delle gustose “mescolanze” di Exposé e classico Tab-Switching. Trovate tutto nei link sotto.

Infine, una domanda: ma Novell crede proprio tanto nel Desktop Linux? Diavolo, vi rendete conto dell’enorme esborso economico che sta affrontando e delle energie (soprattutto di marketing) che sta investendo? Anche se stesse spendendo poco in denaro, un eventuale fallimento sarebbe assolutamente distruttivo, non trovate?

Chi vivrà, vedrà (e mai come ora é il caso di dirlo)…

Eccovi quindi una bella serie di link da cui attingere:

Bhè, non sono riuscito ad attendere e quindi ho visto l’ultimo video della lista prima ancora di finire di scrivere questo post e… c’é da rimanere basiti.
Ci sono finezze grafiche ed effetti che negli altri video non compaiono (forse perché di bassa qualità rispetto a questo): un esempio su tutti é l’effetto di “desaturazione” (alias, decolorazione) per le applicazioni che dovessere “non rispondere più ai comandi”. Una finezza a dir poco stupenda. Quasi quasi faccio crashare FF per il solo gusto di vederlo desaturare :D .

Ovviamente, tutti gli effetti sono SEMPRE GRADUALI: ogni transizione di colore, ogni effetto di deformazione, apparizione, scomparsa… sono tutti GRADUALI e dolci. I pop-up sono quasi “fisici” e viene voglia di toccarli, tanta é la loro “consistenza ottica”.

Xgl, é giusto concludere così, può tramutarsi davvero in una Killer-Application per il Desktop Linux ma… é inutile farsi illusioni: se non si produce software che sappia ben sfruttare tutto questo, gli effetti “spettacolosi” lasceranno il tempo che trovano.

Ora, non ci resta che aspettare (per i più pigri e/o occupati) o smanettare con il CVS (per i più intraprendenti e/o nullafacenti).

, , , , , , ,

Soon, Native GTK+ on MacOSX

Jan 31st

Posted by Detro in IT / Comp-Sci / Code

3 comments


Soon you may be able to execute Gnome/Gtk+ based programs NATIVELLY NATIVELY on Quartz without the X11 Emulation.
Someone (thanks to exist) is working on the porting.

It may be the incipit of a new era for Open Source software on MacOSX. Take a look at this.

One of the most interesting characteristics of Gnome-oriented applications is the coherence between the HIG (Human Interface Guidelines) of Gnome and MacOSX.

Source: Melablog.it and StyleMac.com.

, , , , , , , , ,
« Older Entries