Git says local branch is behind remote branch, but it's not

Question

Scenario:

1. I make a new branch
   
2. hack on it
   
3. commit it
   
4. push it
   
5. hack on it some more
   
6. commit again
   
7. try to push again
   

Git responds:

Updates were rejected because the tip of your current branch is behind its remote counterpart. etc.

I'm the only one hacking on this branch - no one else is touching it. The remote branch is actually behind the local branch. I shouldn't have to pull at all.

(And if I do pull, Git reports conflicts between the two, and forces me to merge the branch into itself)

Why is this (likely) happening? And how can I diagnose/fix it?

To be clear, I'm not branching anywhere, and no one else is working on it:

Remote: Commit A -------- Commit B  

Local:  Commit A -------- Commit B -------- Commit C  

C is a straight continuation of B, no branching involved. But git thinks C is a branch of A:

Remote: Commit A -------- Commit B  

                  ------- Commit C  
                /  
Local:  Commit A -------- Commit B  

It's not; it's a straight continuation of B.

Answer 1

You probably did some history rewriting? Your local branch diverged from the one on the server. Run this command to get a better understanding of what happened:

gitk HEAD @{u}

I would strongly recommend you try to understand where this error is coming from. To fix it, simply run:

git push -f

The -f makes this a “forced push” and overwrites the branch on the server. That is very dangerous when you are working in team. But since you are on your own and sure that your local state is correct this should be fine. You risk losing commit history if that is not the case.