An electronic device with a cache memory and a method of operating the electronic device are provided. The electronic device includes a cache memory including a plurality of cache lines each of which includes a first area with at least one storage space and a second area with at least one storage space, where the at least one storage space of the first area has a first size and the at least one storage space of the second area has a second size different from the first size, and a cache controller for storing the data requested for storage in one of the storage spaces of the first or second area, according to a compression factor associated with the data requested for storage when a request is made to store data in the cache memory.